[Python-Dev] Status of pairing_heap.py?

[Paul Chiusano]

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