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. :-)
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 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