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

**Kevin O'Connor
**
kevin@koconnor.net

*Mon, 24 Jun 2002 21:33:18 -0400*

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. :-)
Cheers,
-Kevin
def heappush(heap, item):
pos = len(heap)
heap.append(None)
while pos:
parentpos = (pos - 1) / 2
parent = heap[parentpos]
if item <= parent:
break
heap[pos] = parent
pos = parentpos
heap[pos] = item
def heappop(heap):
endpos = len(heap) - 1
if endpos <= 0:
return heap.pop()
returnitem = heap[0]
item = heap.pop()
pos = 0
while 1:
child2pos = (pos + 1) * 2
child1pos = child2pos - 1
if child2pos < endpos:
child1 = heap[child1pos]
child2 = heap[child2pos]
if item >= child1 and item >= child2:
break
if child1 > child2:
heap[pos] = child1
pos = child1pos
continue
heap[pos] = child2
pos = child2pos
continue
if child1pos < endpos:
child1 = heap[child1pos]
if child1 > item:
heap[pos] = child1
pos = child1pos
break
heap[pos] = item
return returnitem
--
------------------------------------------------------------------------
| Kevin O'Connor "BTW, IMHO we need a FAQ for |
| kevin@koconnor.net 'IMHO', 'FAQ', 'BTW', etc. !" |
------------------------------------------------------------------------