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=40887&view=markup 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 _______________________________________________ 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
