[Python-checkins] r84412 - python/branches/release27-maint/Doc/library/heapq.rst

raymond.hettinger python-checkins at python.org
Wed Sep 1 23:20:07 CEST 2010


Author: raymond.hettinger
Date: Wed Sep  1 23:20:07 2010
New Revision: 84412

Log:
Cleanup heapq docs

Modified:
   python/branches/release27-maint/Doc/library/heapq.rst

Modified: python/branches/release27-maint/Doc/library/heapq.rst
==============================================================================
--- python/branches/release27-maint/Doc/library/heapq.rst	(original)
+++ python/branches/release27-maint/Doc/library/heapq.rst	Wed Sep  1 23:20:07 2010
@@ -63,45 +63,16 @@
 
    Pop and return the smallest item from the *heap*, and also push the new *item*.
    The heap size doesn't change. If the heap is empty, :exc:`IndexError` is raised.
-   This is more efficient than :func:`heappop` followed by  :func:`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 unless written as part of a conditional replacement::
-
-      if item > heap[0]:
-          item = heapreplace(heap, item)
-
-Example of use:
-
-   >>> from heapq import heappush, heappop
-   >>> heap = []
-   >>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
-   >>> for item in data:
-   ...     heappush(heap, item)
-   ...
-   >>> ordered = []
-   >>> while heap:
-   ...     ordered.append(heappop(heap))
-   ...
-   >>> print ordered
-   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-   >>> data.sort()
-   >>> print data == ordered
-   True
-
-Using a heap to insert items at the correct place in a priority queue:
-
-   >>> heap = []
-   >>> data = [(1, 'J'), (4, 'N'), (3, 'H'), (2, 'O')]
-   >>> for item in data:
-   ...     heappush(heap, item)
-   ...
-   >>> while heap:
-   ...     print heappop(heap)[1]
-   J
-   O
-   H
-   N
+
+   This one step operation is more efficient than a :func:`heappop` followed by
+   :func:`heappush` and can be more appropriate when using a fixed-size heap.
+   The pop/push combination always returns an element from the heap and replaces
+   it with *item*.
+
+   The value returned may be larger than the *item* added.  If that isn't
+   desired, consider using :func:`heappushpop` instead.  Its push/pop
+   combination returns the smaller of the two values, leaving the larger value
+   on the heap.
 
 
 The module also offers three general purpose functions based on heaps.
@@ -152,6 +123,35 @@
 functions.
 
 
+Basic Examples
+--------------
+
+A `heapsort <http://en.wikipedia.org/wiki/Heapsort>`_ can be implemented by
+pushing all values onto a heap and then popping off the smallest values one at a
+time::
+
+   >>> def heapsort(iterable):
+   ...     'Equivalent to sorted(iterable)'
+   ...     h = []
+   ...     for value in iterable:
+   ...         heappush(h, value)
+   ...     return [heappop(h) for i in range(len(h))]
+   ...
+   >>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
+   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
+
+Heap elements can be tuples.  This is useful for assigning comparison values
+(such as task priorities) alongside the main record being tracked::
+
+    >>> h = []
+    >>> heappush(h, (5, 'write code'))
+    >>> heappush(h, (7, 'release product'))
+    >>> heappush(h, (1, 'write spec'))
+    >>> heappush(h, (3, 'create tests'))
+    >>> heappop(h)
+    (1, 'write spec')
+
+
 Priority Queue Implementation Notes
 -----------------------------------
 


More information about the Python-checkins mailing list