[Python-Dev] Status of pairing_heap.py? (original) (raw)

Paul Chiusano paul.chiusano at gmail.com
Sun Nov 5 18:36:35 CET 2006

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 adjustkey() 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

More information about the Python-Dev mailing list