[Python-Dev] Status of pairing_heap.py?

Paul Chiusano paul.chiusano at gmail.com
Sun Oct 29 16:51:01 CET 2006

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:


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
  * 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?


More information about the Python-Dev mailing list