[Python-checkins] python/dist/src/Lib heapq.py,1.6,1.7

[tim_one@users.sourceforge.net]

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

Modified Files:
	heapq.py 
Log Message:
Hmm!  I thought I checked this in before!  Oh well.

Added new heapify() function, which transforms an arbitrary list into a
heap in linear time; that's a fundamental tool for using heaps in real
life <wink>.

Added heapyify() test.  Added a "less naive" N-best algorithm to the test
suite, and noted that this could actually go much faster (building on
heapify()) if we had max-heaps instead of min-heaps (the iterative method
is appropriate when all the data isn't known in advance, but when it is
known in advance the tradeoffs get murkier).


Index: heapq.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/heapq.py,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** heapq.py	2 Aug 2002 20:23:56 -0000	1.6
--- heapq.py	2 Aug 2002 21:48:06 -0000	1.7
***************
*** 14,17 ****
--- 14,18 ----
  item = heappop(heap) # pops the smallest item from the heap
  item = heap[0]       # smallest item on the heap without popping it
+ heapify(heap)        # transform list into a heap, in-place, in linear time
  
  Our API differs from textbook heap algorithms as follows:
***************
*** 137,149 ****
      heap[pos] = item
  
! def heappop(heap):
!     """Pop the smallest item off the heap, maintaining the heap invariant."""
!     endpos = len(heap) - 1
!     if endpos <= 0:
!         return heap.pop()
!     returnitem = heap[0]
!     item = heap.pop()
!     pos = 0
!     # Sift item into position, down from the root, moving the smaller
      # child up, until finding pos such that item <= pos's children.
      childpos = 2*pos + 1    # leftmost child position
--- 138,148 ----
      heap[pos] = item
  
! # The child indices of heap index pos are already heaps, and we want to make
! # a heap at index pos too.
! def _siftdown(heap, pos):
!     endpos = len(heap)
!     assert pos < endpos
!     item = heap[pos]
!     # Sift item into position, down from pos, moving the smaller
      # child up, until finding pos such that item <= pos's children.
      childpos = 2*pos + 1    # leftmost child position
***************
*** 165,169 ****
--- 164,189 ----
          childpos = 2*pos + 1
      heap[pos] = item
+ 
+ def heappop(heap):
+     """Pop the smallest item off the heap, maintaining the heap invariant."""
+     lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
+     if heap:
+         returnitem = heap[0]
+         heap[0] = lastelt
+         _siftdown(heap, 0)
+     else:
+         returnitem = lastelt
      return returnitem
+ 
+ def heapify(heap):
+     """Transform list heap into a heap, in-place, in O(len(heap)) time."""
+     n = len(heap)
+     # Transform bottom-up.  The largest index there's any point to looking at
+     # is the largest with a child index in-range, so must have 2*i + 1 < n,
+     # or i < (n-1)/2.  If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
+     # j-1 is the largest, which is n//2 - 1.  If n is odd = 2*j+1, this is
+     # (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
+     for i in xrange(n//2 - 1, -1, -1):
+         _siftdown(heap, i)
  
  if __name__ == "__main__":