Added new heapreplace(heap, item) function, to pop (and return) the
currently-smallest value, and add item, in one gulp. See the second
N-Best algorithm in the test suite for a natural use.
diff --git a/Lib/heapq.py b/Lib/heapq.py
index 278ba24..23f8be5 100644
--- a/Lib/heapq.py
+++ b/Lib/heapq.py
@@ -14,6 +14,8 @@
item = heappop(heap) # pops the smallest item from the heap
item = heap[0] # smallest item on the heap without popping it
heapify(x) # transforms list into a heap, in-place, in linear time
+item = heapreplace(heap, item) # pops and returns smallest item, and adds
+ # new item; the heap size is unchanged
Our API differs from textbook heap algorithms as follows:
@@ -140,6 +142,22 @@
returnitem = lastelt
return returnitem
+def heapreplace(heap, item):
+ """Pop and return the current smallest value, and add the new item.
+
+ This is more efficient than heappop() followed by heappush(), and can be
+ more appropriate when using a fixed-size heap. Note that the value
+ returned may be larger than item! That constrains reasonable uses of
+ this routine.
+ """
+
+ if heap:
+ returnitem = heap[0]
+ heap[0] = item
+ _siftup(heap, 0)
+ return returnitem
+ heap.pop() # raise IndexError
+
def heapify(x):
"""Transform list into a heap, in-place, in O(len(heap)) time."""
n = len(x)