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

Josiah Carlson jcarlson at uci.edu
Sun Nov 5 19:24:45 CET 2006

"Paul Chiusano" <paul.chiusano at gmail.com> wrote:

> 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?

I mean a Python list. The trick is to implement a sequence API that keeps track of the position of any 'pair'. That is, ph[posn] will return a 'pair' object, but when you perform ph[posn] = pair, you also update a mapping; ph.mapping[pair.value] = posn . With a few other bits, one can use heapq directly and get all of the features of the pairing heap API without keeping an explicit tree with links, etc.

In terms of running time, adjust_key, delete, and extract(0) are all O(logn), meld is O(min(n+m, mlog(n+m))), empty and peek are O(1), values is O(n), and extract_all is O(nlogn) but uses list.sort() rather than repeatedly pulling from the heap (heapq's documentation suggests this is faster in terms of comparisions, but likely very much faster in terms of actual running time).

Attached is a sample implementation using this method with a small test example. It may or may not use less memory than the sandbox pairing_heap.py, and using bare lists rather than pairs may result in less memory overall (if there exists a list "free list"), but this should give you something to start with.

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 > > -------------- next part -------------- A non-text attachment was scrubbed... Name: pair_heap.py Type: application/octet-stream Size: 5377 bytes Desc: not available Url : http://mail.python.org/pipermail/python-dev/attachments/20061105/62f57d3a/attachment.obj

More information about the Python-Dev mailing list