[Python-Dev] Status of pairing_heap.py?

[Paul Chiusano]

Hi Martin,

Yes, I'm familiar with the heapq module, but it doesn't do all that
I'd like. The main functionality I am looking for is the ability to
adjust the value of an item in the heap and delete items from the
heap. There's a lot of heap applications where this is useful. (I
might even say most heap applications!)

To support this, the insert method needs to return a reference to an
object which I can then pass to adjust_key() and delete() methods.
It's extremely difficult to have this functionality with array-based
heaps because the index of an item in the array changes as items are
inserted and removed.

I guess I don't need a pairing heap, but of the pointer-based heaps
I've looked at, pairing heaps seem to be the simplest while still
having good complexity guarantees.

> Anyway, the immediate author of this code is Dan Stutzbach (as
> Raymond Hettinger's checkin message says); you probably should
> contact him to find out whether the project is still alive.

Okay, I'll do that. What needs to be done to move the project along
and possibly get a pairing heap incorporated into a future version of
python?

Best,
Paul

On 11/4/06, "Martin v. Löwis" <martin at v.loewis.de> wrote:
> Paul Chiusano schrieb:
> > I was looking for a good pairing_heap implementation and came across
> > one that had apparently been checked in a couple years ago (!).
>
> Have you looked at the heapq module? What application do you have
> for a pairing heap that you can't do readily with the heapq module?
>
> Anyway, the immediate author of this code is Dan Stutzbach (as
> Raymond Hettinger's checkin message says); you probably should
> contact him to find out whether the project is still alive.
>
> Regards,
> Martin
>