[Python-Dev] Status of pairing_heap.py?
Josiah Carlson
jcarlson at uci.edu
Sat Nov 4 21:50:51 CET 2006
"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
More information about the Python-Dev
mailing list