[Python-checkins] python/dist/src/Doc/lib libheapq.tex,1.2,1.3

2002年8月03日 11:02:11 -0700

Update of /cvsroot/python/python/dist/src/Doc/lib
In directory usw-pr-cvs1:/tmp/cvs-serv307/python/Doc/lib
Modified Files:
	libheapq.tex 
Log Message:
Document new heapify() function.
Index: libheapq.tex
===================================================================
RCS file: /cvsroot/python/python/dist/src/Doc/lib/libheapq.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** libheapq.tex	2 Aug 2002 19:46:42 -0000	1.2
--- libheapq.tex	3 Aug 2002 18:02:09 -0000	1.3
***************
*** 26,30 ****
 index for a node and the indexes for its children slightly less
 obvious, but is more suitable since Python uses zero-based indexing.
! (b) Our pop method returns the smallest item, not the largest.

 These two make it possible to view the heap as a regular Python list
--- 26,32 ----
 index for a node and the indexes for its children slightly less
 obvious, but is more suitable since Python uses zero-based indexing.
! (b) Our pop method returns the smallest item, not the largest (called a
! "min heap" in textbooks; a "max heap" is more common in texts because
! of its suitability for in-place sorting).

 These two make it possible to view the heap as a regular Python list
***************
*** 32,36 ****
 \code{\var{heap}.sort()} maintains the heap invariant!

! To create a heap, use a list initialized to \code{[]}.

 The following functions are provided:
--- 34,39 ----
 \code{\var{heap}.sort()} maintains the heap invariant!

! To create a heap, use a list initialized to \code{[]}, or you can
! transform a populated list into a heap via function \function{heapify()}.

 The following functions are provided:
***************
*** 46,49 ****
--- 49,56 ----
 \end{funcdesc}

+ \begin{funcdesc}{heapify}{x}
+ Transform list \var{x} into a heap, in-place, in linear time.
+ \end{funcdesc}
+ 
 Example of use:

***************
*** 54,62 ****
 >>> for item in data:
 ... heappush(heap, item)
! ... 
 >>> sorted = []
 >>> while heap:
 ... sorted.append(heappop(heap))
! ... 
 >>> print sorted
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
--- 61,69 ----
 >>> for item in data:
 ... heappush(heap, item)
! ...
 >>> sorted = []
 >>> while heap:
 ... sorted.append(heappop(heap))
! ...
 >>> print sorted
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
***************
*** 64,68 ****
 >>> print data == sorted
 True
! >>> 
 \end{verbatim}

--- 71,75 ----
 >>> print data == sorted
 True
! >>>
 \end{verbatim}