# [Python-Dev] Priority queue (binary heap) python code

**Oren Tirosh
**
oren-py-d@hishome.net

*Tue, 25 Jun 2002 02:52:03 -0400*

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!
Oren