[Python-checkins] python/dist/src/Lib heapq.py,1.10,1.11

[tim_one@users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Lib
In directory usw-pr-cvs1:/tmp/cvs-serv29493/python/Lib

Modified Files:
	heapq.py 
Log Message:
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.


Index: heapq.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/heapq.py,v
retrieving revision 1.10
retrieving revision 1.11
diff -C2 -d -r1.10 -r1.11
*** heapq.py	3 Aug 2002 09:56:52 -0000	1.10
--- heapq.py	3 Aug 2002 10:10:10 -0000	1.11
***************
*** 15,18 ****
--- 15,20 ----
  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,143 ****
--- 142,161 ----
          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):