On Mon, Jun 24, 2002 at 09:33:18PM -0400, Kevin O'Connor wrote:
I often find myself needing priority queues in python, and I've finally broken down and written a simple implementation. Previously I've used sorted lists (via bisect) to get the job done, but the heap code significantly improves performance. There are C based implementations, but the effort of compiling in an extension often isn't worth the effort. I'm including the code here for everyone's amusement.
Any chance something like this could make it into the standard python library? It would save a lot of time for lazy people like myself. :-)
A sorted list is a much more general-purpose data structure than a priority queue and can be used to implement a priority queue. It offers almost the same asymptotic performance:
sorted list using splay tree (amortized): insert: O(log n) pop: O(log n) peek: O(log n)
priority queue using binary heap: insert: O(log n) pop: O(log n) peek: O(1)
The only advantage of a heap is O(1) peek which doesn't seem so critical. It may also have somewhat better performance by a constant factor because it uses an array rather than allocating node structures. But the internal order of a heap-based priority queue is very non-intuitive and quite useless for other purposes while a sorted list is, umm..., sorted!