diff options
| -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 8e6fd2d..416ec2c 100644 --- a/Doc/library/heapq.rst +++ b/Doc/library/heapq.rst @@ -63,45 +63,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)) - ... - >>> 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 + 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 @@ 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 ----------------------------------- |