[Magnus Lie Hetland]
I see that heapq is now in the libraries -- great!
Just one thought: If I want to use this library in an algorithm such as, say, Dijkstra's single-source shortest path algorithms, I would need an additional operation, the deacrease-key operation
You'd need more than just that <wink>.
(as far as I can see, the heapreplace only works with index 0 -- wy is that?)
heapreplace() is emphatically not a decrease-key operation. It's equivalent to a pop-min *followed by* a push, which combination is often called a "hold" operation. The value added may very well be larger than the value popped, and, e.g., the example of an efficient N-Best queue in the test file relies on this. Hold is an extremely common operation in some kinds of event simulations too, where it's also most common to push a value larger than the one popped (e.g., when the queue is ordered by scheduled time, and the item pushed is a follow-up event to the one getting popped).
E.g.:
def heapdecrease(heap, index, item): """ Replace an item at a given index with a smaller one.
May be used to implement the standard priority queue method heap-decrease-key, useful, for instance, in several graph algorithms. """ assert item <= heap[index]
That's the opposite of what heapreplace() usually sees.
heap[index] = item _siftdown(heap, 0, index)
Something might perhaps be useful to include in the library...
I really don't see how -- you generally have no way to know the correct index short of O(N) search. This representation of priority queue is well-known to be sub-optimal for applications requiring frequent decrease-key (Fibonacci heaps were desgined for it, though, and pairing heaps are reported to run faster than Fibonacci heaps in practice despite that one of the PH inventors eventually proved that decrease-key can destroy PH's otherwise good worst-case behavior).
Or, perhaps, the _siftup and _siftdown methods don't have to be private?
You really have to know what you're doing to use them correctly, and it's dubious that _siftup calls _siftdown now (it's most convenient *given* all the uses made of them right now, but, e.g., if a "delete at arbitrary index" function were to be added, _siftdown and _siftup could stand to be refactored -- exposing them would inhibit future improvements).
In addition, I guess one would have to implement a sequence class that maintained a map from values to heap indices to be able to use heapdecrease in any useful way (otherwise, how would you know which index to use?).
Bingo. All the internal heap manipulations would have to know about this mapping too, in order to keep the indices up to date as it moved items up and down in the queue. If want you want is frequent decrease-key, you don't want this implementation of priority queues at all.