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

[Kevin O'Connor]

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. !"    |
 ------------------------------------------------------------------------