[Python-checkins] python/dist/src/Lib heapq.py,1.4,1.5

[tim_one@users.sourceforge.net]

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

Modified Files:
	heapq.py 
Log Message:
heappop():  Added comments; simplified and sped the code.


Index: heapq.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/heapq.py,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** heapq.py	2 Aug 2002 19:45:37 -0000	1.4
--- heapq.py	2 Aug 2002 20:09:14 -0000	1.5
***************
*** 143,167 ****
      item = heap.pop()
      pos = 0
!     while True:
!         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
--- 143,165 ----
      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
!     while childpos < endpos:
!         # Set childpos and child to reflect smaller child.
!         child = heap[childpos]
!         rightpos = childpos + 1
!         if rightpos < endpos:
!             rightchild = heap[rightpos]
!             if rightchild < child:
!                 childpos = rightpos
!                 child = rightchild
!         # If item is no larger than smaller child, we're done, else
!         # move the smaller child up.
!         if item <= child:
!             break
!         heap[pos] = child
!         pos = childpos
!         childpos = 2*pos + 1
      heap[pos] = item
      return returnitem