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[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
I have read (or at least skimmed) this entire thread now. After I reconstructed the algorithm in my head, I went back to Kevin's code; I admire the compactness of his code. I believe that this would make a good addition to the standard library, as a friend of the bisect module. The only change I would make would be to make heap[0] the lowest value rather than the highest. (That's one thing that I liked better about François Pinard's version, but a class seems too heavy for this, just like it is overkill for bisect [*]. Oh, and maybe we can borrow a few lines of François's description of the algorithm. :-) I propose to call it heapq.py. (Got a better name? Now or never.) [*] Afterthought: this could be made into an new-style class by adding something like this to the end of module: class heapq(list): __slots__ = [] heappush = heappush heappop = heappop A similar addition could easily be made to the bisect module. But this is very different from François' class, which hides the other list methods. --Guido van Rossum (home page: http://www.python.org/~guido/)