[Python-Dev] Status of pairing_heap.py?

[Paul Chiusano]

> It is not required.  If you are careful, you can implement a pairing
> heap with a structure combining a dictionary and list.

That's interesting. Can you give an overview of how you can do that? I
can't really picture it. You can support all the pairing heap
operations with the same complexity guarantees? Do you mean a linked
list here or an array?

Paul

On 11/4/06, Josiah Carlson <jcarlson at uci.edu> wrote:
>
> "Martin v. Löwis" <martin at v.loewis.de> wrote:
> > Paul Chiusano schrieb:
> > > 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 see.
>
> It is not required.  If you are careful, you can implement a pairing
> heap with a structure combining a dictionary and list.  It requires that
> all values be unique and hashable, but it is possible (I developed one
> for a commercial project).
>
> If other people find the need for it, I could rewrite it (can't release
> the closed source).  It would use far less memory than the pairing heap
> implementation provided in the sandbox, and could be converted to C if
> desired and/or required.  On the other hand, I've found the pure Python
> version to be fast enough for most things I've needed it for.
>
>  - Josiah
>
>