Kevin O'Connor <kevin@koconnor.net>:
I often find myself needing priority queues in python, and I've finally broken down and written a simple implementation.
[snip] 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?) 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] 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...) -- Magnus Lie Hetland The Anygui Project http://hetland.org http://anygui.org