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

[Guido van Rossum]

> 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/)