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

[Oren Tirosh]

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