I was looking for a good pairing_heap implementation and came across one that had apparently been checked in a couple years ago (!). Here is the full link:
http://svn.python.org/view/sandbox/trunk/collections/pairing_heap.py?rev=408...
I was just wondering about the status of this implementation. The api looks pretty good to me -- it's great that the author decided to have the insert method return a node reference which can then be passed to delete and adjust_key. It's a bit of a pain to implement that functionality, but it's extremely useful for a number of applications.
If that project is still alive, I have a couple api suggestions:
* Add a method which nondestructively yields the top K elements of the heap. This would work by popping the top k elements of the heap into a list, then reinserting those elements in reverse order. By reinserting the sorted elements in reverse order, the top of the heap is essentially a sorted linked list, so if the exact operation is repeated again, the removals take contant time rather than amortized logarthmic. * So, for example: if we have a min heap, the topK method would pop K elements from the heap, say they are {1, 3, 5, 7}, then do insert(7), followed by insert(5), ... insert(1). * Even better might be if this operation avoided having to allocate new heap nodes, and just reused the old ones. * I'm not sure if adjust_key should throw an exception if the key adjustment is in the wrong direction. Perhaps it should just fall back on deleting and reinserting that node?
Paul
Paul Chiusano schrieb:
I was looking for a good pairing_heap implementation and came across one that had apparently been checked in a couple years ago (!).
Have you looked at the heapq module? What application do you have for a pairing heap that you can't do readily with the heapq module?
Anyway, the immediate author of this code is Dan Stutzbach (as Raymond Hettinger's checkin message says); you probably should contact him to find out whether the project is still alive.
Regards, Martin
Hi Martin,
Yes, I'm familiar with the heapq module, but it doesn't do all that I'd like. The main functionality I am looking for is the ability to adjust the value of an item in the heap and delete items from the heap. There's a lot of heap applications where this is useful. (I might even say most heap applications!)
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 guess I don't need a pairing heap, but of the pointer-based heaps I've looked at, pairing heaps seem to be the simplest while still having good complexity guarantees.
Anyway, the immediate author of this code is Dan Stutzbach (as Raymond Hettinger's checkin message says); you probably should contact him to find out whether the project is still alive.
Okay, I'll do that. What needs to be done to move the project along and possibly get a pairing heap incorporated into a future version of python?
Best, Paul
On 11/4/06, "Martin v. Löwis" martin@v.loewis.de wrote:
Paul Chiusano schrieb:
I was looking for a good pairing_heap implementation and came across one that had apparently been checked in a couple years ago (!).
Have you looked at the heapq module? What application do you have for a pairing heap that you can't do readily with the heapq module?
Anyway, the immediate author of this code is Dan Stutzbach (as Raymond Hettinger's checkin message says); you probably should contact him to find out whether the project is still alive.
Regards, Martin
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.
Okay, I'll do that. What needs to be done to move the project along and possibly get a pairing heap incorporated into a future version of python?
As a starting point, I think the implementation should get packaged as an independent library, and be listed in the Cheeseshop for a few years. If then there's wide interest in including it into Python, it should be reconsidered. At that point, the then-authors of the package will have to sign a contributor form.
Regards, Martin
"Martin v. Löwis" martin@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
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@uci.edu wrote:
"Martin v. Löwis" martin@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
"Paul Chiusano" paul.chiusano@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.
- Josiah
Paul
On 11/4/06, Josiah Carlson jcarlson@uci.edu wrote:
"Martin v. Löwis" martin@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
participants (3)
-
"Martin v. Löwis" -
Josiah Carlson -
Paul Chiusano