summaryrefslogtreecommitdiffstats
path: root/Doc/library/heapq.rst
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2010-09-01 21:27:31 (GMT)
committerRaymond Hettinger <python@rcn.com>2010-09-01 21:27:31 (GMT)
commit6f80b4c8b7be1277f91fc7e923b200b83bc4ad88 (patch)
treea4756a65ac116172b56608c63d688b24ecf511f8 /Doc/library/heapq.rst
parentc73b909a2b31f503278202148bfa85d9ccf085a4 (diff)
downloadcpython-6f80b4c8b7be1277f91fc7e923b200b83bc4ad88.zip
cpython-6f80b4c8b7be1277f91fc7e923b200b83bc4ad88.tar.gz
cpython-6f80b4c8b7be1277f91fc7e923b200b83bc4ad88.tar.bz2
Cleanup heapq docs
Diffstat (limited to 'Doc/library/heapq.rst')
-rw-r--r--Doc/library/heapq.rst74
1 files changed, 37 insertions, 37 deletions
diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst
index f5d62c7..49e3bf3 100644
--- a/Doc/library/heapq.rst
+++ b/Doc/library/heapq.rst
@@ -61,45 +61,16 @@ The following functions are provided:
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)
+ 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*.
-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))
- ...
- >>> ordered
- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
- >>> data.sort()
- >>> 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
+ 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.
@@ -139,6 +110,35 @@ values, it is more efficient to use the :func:`sorted` function. Also, when
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
-----------------------------------