[Python-Dev] Status of pairing_heap.py? (original) (raw)
Paul Chiusano paul.chiusano at gmail.com
Sun Oct 29 16:51:01 CET 2006
- Previous message: [Python-Dev] PyCon: proposals due by Tuesday 10/31
- Next message: [Python-Dev] PEP: Adding data-type objects to Python
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
I was looking for a good pairing_heap implementation and came across one that had apparently been checked in a couple years ago (!). Here is the full link:
http://svn.python.org/view/sandbox/trunk/collections/pairing_heap.py?rev=40887&view=markup
I was just wondering about the status of this implementation. The api looks pretty good to me -- it's great that the author decided to have the insert method return a node reference which can then be passed to delete and adjust_key. It's a bit of a pain to implement that functionality, but it's extremely useful for a number of applications.
If that project is still alive, I have a couple api suggestions:
- Add a method which nondestructively yields the top K elements of the
heap. This would work by popping the top k elements of the heap into a
list, then reinserting those elements in reverse order. By reinserting
the sorted elements in reverse order, the top of the heap is
essentially a sorted linked list, so if the exact operation is
repeated again, the removals take contant time rather than amortized
logarthmic.
- So, for example: if we have a min heap, the topK method would pop K elements from the heap, say they are {1, 3, 5, 7}, then do insert(7), followed by insert(5), ... insert(1).
- Even better might be if this operation avoided having to allocate new heap nodes, and just reused the old ones.
- I'm not sure if adjust_key should throw an exception if the key adjustment is in the wrong direction. Perhaps it should just fall back on deleting and reinserting that node?
Paul
- Previous message: [Python-Dev] PyCon: proposals due by Tuesday 10/31
- Next message: [Python-Dev] PEP: Adding data-type objects to Python
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]