"Paul Chiusano" firstname.lastname@example.org 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.
On 11/4/06, Josiah Carlson email@example.com wrote:
"Martin v. Löwis" firstname.lastname@example.org 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.
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.