diff options
Diffstat (limited to 'Doc/library/heapq.rst')
| -rw-r--r-- | Doc/library/heapq.rst | 224 |
1 files changed, 224 insertions, 0 deletions
diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst new file mode 100644 index 0000000..2d38c26 --- /dev/null +++ b/Doc/library/heapq.rst @@ -0,0 +1,224 @@ + +:mod:`heapq` --- Heap queue algorithm +===================================== + +.. module:: heapq + :synopsis: Heap queue algorithm (a.k.a. priority queue). +.. moduleauthor:: Kevin O'Connor +.. sectionauthor:: Guido van Rossum <guido@python.org> +.. sectionauthor:: François Pinard + + +.. % Theoretical explanation: + +.. versionadded:: 2.3 + +This module provides an implementation of the heap queue algorithm, also known +as the priority queue algorithm. + +Heaps are arrays for which ``heap[k] <= heap[2*k+1]`` and ``heap[k] <= +heap[2*k+2]`` for all *k*, counting elements from zero. For the sake of +comparison, non-existing elements are considered to be infinite. The +interesting property of a heap is that ``heap[0]`` is always its smallest +element. + +The API below differs from textbook heap algorithms in two aspects: (a) We use +zero-based indexing. This makes the relationship between the 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 without +surprises: ``heap[0]`` is the smallest item, and ``heap.sort()`` maintains the +heap invariant! + +To create a heap, use a list initialized to ``[]``, or you can transform a +populated list into a heap via function :func:`heapify`. + +The following functions are provided: + + +.. function:: heappush(heap, item) + + Push the value *item* onto the *heap*, maintaining the heap invariant. + + +.. function:: heappop(heap) + + Pop and return the smallest item from the *heap*, maintaining the heap + invariant. If the heap is empty, :exc:`IndexError` is raised. + + +.. function:: heapify(x) + + Transform list *x* into a heap, in-place, in linear time. + + +.. function:: heapreplace(heap, item) + + 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 + >>> + +The module also offers three general purpose functions based on heaps. + + +.. function:: merge(*iterables) + + Merge multiple sorted inputs into a single sorted output (for example, merge + timestamped entries from multiple log files). Returns an iterator over over the + sorted values. + + Similar to ``sorted(itertools.chain(*iterables))`` but returns an iterable, does + not pull the data into memory all at once, and assumes that each of the input + streams is already sorted (smallest to largest). + + .. versionadded:: 2.6 + + +.. function:: nlargest(n, iterable[, key]) + + Return a list with the *n* largest elements from the dataset defined by + *iterable*. *key*, if provided, specifies a function of one argument that is + used to extract a comparison key from each element in the iterable: + ``key=str.lower`` Equivalent to: ``sorted(iterable, key=key, + reverse=True)[:n]`` + + .. versionadded:: 2.4 + + .. versionchanged:: 2.5 + Added the optional *key* argument. + + +.. function:: nsmallest(n, iterable[, key]) + + Return a list with the *n* smallest elements from the dataset defined by + *iterable*. *key*, if provided, specifies a function of one argument that is + used to extract a comparison key from each element in the iterable: + ``key=str.lower`` Equivalent to: ``sorted(iterable, key=key)[:n]`` + + .. versionadded:: 2.4 + + .. versionchanged:: 2.5 + Added the optional *key* argument. + +The latter two functions perform best for smaller values of *n*. For larger +values, it is more efficient to use the :func:`sorted` function. Also, when +``n==1``, it is more efficient to use the builtin :func:`min` and :func:`max` +functions. + + +Theory +------ + +(This explanation is due to François Pinard. The Python code for this module +was contributed by Kevin O'Connor.) + +Heaps are arrays for which ``a[k] <= a[2*k+1]`` and ``a[k] <= a[2*k+2]`` for all +*k*, counting elements from 0. For the sake of comparison, non-existing +elements are considered to be infinite. The interesting property of a heap is +that ``a[0]`` is always its smallest element. + +The strange invariant above is meant to be an efficient memory representation +for a tournament. The numbers below are *k*, not ``a[k]``:: + + 0 + + 1 2 + + 3 4 5 6 + + 7 8 9 10 11 12 13 14 + + 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 + +In the tree above, each cell *k* is topping ``2*k+1`` and ``2*k+2``. In an usual +binary tournament we see in sports, each cell is the winner over the two cells +it tops, and we can trace the winner down the tree to see all opponents s/he +had. However, in many computer applications of such tournaments, we do not need +to trace the history of a winner. To be more memory efficient, when a winner is +promoted, we try to replace it by something else at a lower level, and the rule +becomes that a cell and the two cells it tops contain three different items, but +the top cell "wins" over the two topped cells. + +If this heap invariant is protected at all time, index 0 is clearly the overall +winner. The simplest algorithmic way to remove it and find the "next" winner is +to move some loser (let's say cell 30 in the diagram above) into the 0 position, +and then percolate this new 0 down the tree, exchanging values, until the +invariant is re-established. This is clearly logarithmic on the total number of +items in the tree. By iterating over all items, you get an O(n log n) sort. + +A nice feature of this sort is that you can efficiently insert new items while +the sort is going on, provided that the inserted items are not "better" than the +last 0'th element you extracted. This is especially useful in simulation +contexts, where the tree holds all incoming events, and the "win" condition +means the smallest scheduled time. When an event schedule other events for +execution, they are scheduled into the future, so they can easily go into the +heap. So, a heap is a good structure for implementing schedulers (this is what +I used for my MIDI sequencer :-). + +Various structures for implementing schedulers have been extensively studied, +and heaps are good for this, as they are reasonably speedy, the speed is almost +constant, and the worst case is not much different than the average case. +However, there are other representations which are more efficient overall, yet +the worst cases might be terrible. + +Heaps are also very useful in big disk sorts. You most probably all know that a +big sort implies producing "runs" (which are pre-sorted sequences, which size is +usually related to the amount of CPU memory), followed by a merging passes for +these runs, which merging is often very cleverly organised [#]_. It is very +important that the initial sort produces the longest runs possible. Tournaments +are a good way to that. If, using all the memory available to hold a +tournament, you replace and percolate items that happen to fit the current run, +you'll produce runs which are twice the size of the memory for random input, and +much better for input fuzzily ordered. + +Moreover, if you output the 0'th item on disk and get an input which may not fit +in the current tournament (because the value "wins" over the last output value), +it cannot fit in the heap, so the size of the heap decreases. The freed memory +could be cleverly reused immediately for progressively building a second heap, +which grows at exactly the same rate the first heap is melting. When the first +heap completely vanishes, you switch heaps and start a new run. Clever and +quite effective! + +In a word, heaps are useful memory structures to know. I use them in a few +applications, and I think it is good to keep a 'heap' module around. :-) + +.. rubric:: Footnotes + +.. [#] The disk balancing algorithms which are current, nowadays, are more annoying + than clever, and this is a consequence of the seeking capabilities of the disks. + On devices which cannot seek, like big tape drives, the story was quite + different, and one had to be very clever to ensure (far in advance) that each + tape movement will be the most effective possible (that is, will best + participate at "progressing" the merge). Some tapes were even able to read + backwards, and this was also used to avoid the rewinding time. Believe me, real + good tape sorts were quite spectacular to watch! From all times, sorting has + always been a Great Art! :-) + |