> 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/)
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4