Kevin O'Connor email@example.com:
I often find myself needing priority queues in python, and I've finally broken down and written a simple implementation.
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 (as far as I can see, the heapreplace only works with index 0 -- wy is that?)
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] heap[index] = item _siftdown(heap, 0, index)
Something might perhaps be useful to include in the library... Or, perhaps, the _siftup and _siftdown methods don't have to be private?
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?). That, however, I guess is not something that would be 'at home' in the heapq module. (Perhaps that is argument enough to avoid including heapdecrease as well? Oh, well...)