> 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 <[EMAIL PROTECTED]> wrote: > > "Martin v. Löwis" <[EMAIL PROTECTED]> 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 > > _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
