diff options
author | Raymond Hettinger <python@rcn.com> | 2010-09-01 21:27:31 (GMT) |
---|---|---|
committer | Raymond Hettinger <python@rcn.com> | 2010-09-01 21:27:31 (GMT) |
commit | 6f80b4c8b7be1277f91fc7e923b200b83bc4ad88 (patch) | |
tree | a4756a65ac116172b56608c63d688b24ecf511f8 /Doc | |
parent | c73b909a2b31f503278202148bfa85d9ccf085a4 (diff) | |
download | cpython-6f80b4c8b7be1277f91fc7e923b200b83bc4ad88.zip cpython-6f80b4c8b7be1277f91fc7e923b200b83bc4ad88.tar.gz cpython-6f80b4c8b7be1277f91fc7e923b200b83bc4ad88.tar.bz2 |
Cleanup heapq docs
Diffstat (limited to 'Doc')
-rw-r--r-- | Doc/library/heapq.rst | 74 |
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 ----------------------------------- |