Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 1 | \section{\module{heapq} --- |
| 2 | Heap queue algorithm} |
| 3 | |
| 4 | \declaremodule{standard}{heapq} |
| 5 | \modulesynopsis{Heap queue algorithm (a.k.a. priority queue).} |
Fred Drake | 1acab69 | 2002-08-02 19:46:42 +0000 | [diff] [blame] | 6 | \moduleauthor{Kevin O'Connor}{} |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 7 | \sectionauthor{Guido van Rossum}{guido@python.org} |
Fred Drake | 1acab69 | 2002-08-02 19:46:42 +0000 | [diff] [blame] | 8 | % Theoretical explanation: |
| 9 | \sectionauthor{Fran\c cois Pinard}{} |
| 10 | \versionadded{2.3} |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 11 | |
| 12 | |
| 13 | This module provides an implementation of the heap queue algorithm, |
| 14 | also known as the priority queue algorithm. |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 15 | |
| 16 | Heaps are arrays for which |
| 17 | \code{\var{heap}[\var{k}] <= \var{heap}[2*\var{k}+1]} and |
| 18 | \code{\var{heap}[\var{k}] <= \var{heap}[2*\var{k}+2]} |
| 19 | for all \var{k}, counting elements from zero. For the sake of |
| 20 | comparison, non-existing elements are considered to be infinite. The |
| 21 | interesting property of a heap is that \code{\var{heap}[0]} is always |
| 22 | its smallest element. |
| 23 | |
| 24 | The API below differs from textbook heap algorithms in two aspects: |
| 25 | (a) We use zero-based indexing. This makes the relationship between the |
| 26 | index for a node and the indexes for its children slightly less |
| 27 | obvious, but is more suitable since Python uses zero-based indexing. |
Tim Peters | 6e0da82 | 2002-08-03 18:02:09 +0000 | [diff] [blame] | 28 | (b) Our pop method returns the smallest item, not the largest (called a |
| 29 | "min heap" in textbooks; a "max heap" is more common in texts because |
| 30 | of its suitability for in-place sorting). |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 31 | |
| 32 | These two make it possible to view the heap as a regular Python list |
| 33 | without surprises: \code{\var{heap}[0]} is the smallest item, and |
| 34 | \code{\var{heap}.sort()} maintains the heap invariant! |
| 35 | |
Tim Peters | 6e0da82 | 2002-08-03 18:02:09 +0000 | [diff] [blame] | 36 | To create a heap, use a list initialized to \code{[]}, or you can |
| 37 | transform a populated list into a heap via function \function{heapify()}. |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 38 | |
| 39 | The following functions are provided: |
| 40 | |
| 41 | \begin{funcdesc}{heappush}{heap, item} |
| 42 | Push the value \var{item} onto the \var{heap}, maintaining the |
| 43 | heap invariant. |
| 44 | \end{funcdesc} |
| 45 | |
| 46 | \begin{funcdesc}{heappop}{heap} |
| 47 | Pop and return the smallest item from the \var{heap}, maintaining the |
Guido van Rossum | b286591 | 2002-08-07 18:56:08 +0000 | [diff] [blame] | 48 | heap invariant. If the heap is empty, \exception{IndexError} is raised. |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 49 | \end{funcdesc} |
| 50 | |
Tim Peters | 6e0da82 | 2002-08-03 18:02:09 +0000 | [diff] [blame] | 51 | \begin{funcdesc}{heapify}{x} |
| 52 | Transform list \var{x} into a heap, in-place, in linear time. |
| 53 | \end{funcdesc} |
| 54 | |
Tim Peters | 0ad679f | 2002-08-03 18:53:28 +0000 | [diff] [blame] | 55 | \begin{funcdesc}{heapreplace}{heap, item} |
| 56 | Pop and return the smallest item from the \var{heap}, and also push |
| 57 | the new \var{item}. The heap size doesn't change. |
Guido van Rossum | b286591 | 2002-08-07 18:56:08 +0000 | [diff] [blame] | 58 | If the heap is empty, \exception{IndexError} is raised. |
Tim Peters | 0ad679f | 2002-08-03 18:53:28 +0000 | [diff] [blame] | 59 | This is more efficient than \function{heappop()} followed |
| 60 | by \function{heappush()}, and can be more appropriate when using |
| 61 | a fixed-size heap. Note that the value returned may be larger |
Raymond Hettinger | 28224f8 | 2004-06-20 09:07:53 +0000 | [diff] [blame] | 62 | than \var{item}! That constrains reasonable uses of this routine |
Raymond Hettinger | 8158e84 | 2004-09-06 07:04:09 +0000 | [diff] [blame] | 63 | unless written as part of a conditional replacement: |
Raymond Hettinger | 28224f8 | 2004-06-20 09:07:53 +0000 | [diff] [blame] | 64 | \begin{verbatim} |
Raymond Hettinger | 8158e84 | 2004-09-06 07:04:09 +0000 | [diff] [blame] | 65 | if item > heap[0]: |
| 66 | item = heapreplace(heap, item) |
Raymond Hettinger | 28224f8 | 2004-06-20 09:07:53 +0000 | [diff] [blame] | 67 | \end{verbatim} |
Tim Peters | 0ad679f | 2002-08-03 18:53:28 +0000 | [diff] [blame] | 68 | \end{funcdesc} |
| 69 | |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 70 | Example of use: |
| 71 | |
| 72 | \begin{verbatim} |
| 73 | >>> from heapq import heappush, heappop |
| 74 | >>> heap = [] |
| 75 | >>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0] |
| 76 | >>> for item in data: |
| 77 | ... heappush(heap, item) |
Tim Peters | 6e0da82 | 2002-08-03 18:02:09 +0000 | [diff] [blame] | 78 | ... |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 79 | >>> sorted = [] |
| 80 | >>> while heap: |
| 81 | ... sorted.append(heappop(heap)) |
Tim Peters | 6e0da82 | 2002-08-03 18:02:09 +0000 | [diff] [blame] | 82 | ... |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 83 | >>> print sorted |
| 84 | [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
| 85 | >>> data.sort() |
| 86 | >>> print data == sorted |
| 87 | True |
Tim Peters | 6e0da82 | 2002-08-03 18:02:09 +0000 | [diff] [blame] | 88 | >>> |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 89 | \end{verbatim} |
| 90 | |
Raymond Hettinger | 33ecffb | 2004-06-10 05:03:17 +0000 | [diff] [blame] | 91 | The module also offers two general purpose functions based on heaps. |
| 92 | |
Raymond Hettinger | 4901a1f | 2004-12-02 08:59:14 +0000 | [diff] [blame] | 93 | \begin{funcdesc}{nlargest}{n, iterable\optional{, key}} |
Raymond Hettinger | 33ecffb | 2004-06-10 05:03:17 +0000 | [diff] [blame] | 94 | Return a list with the \var{n} largest elements from the dataset defined |
Raymond Hettinger | 4901a1f | 2004-12-02 08:59:14 +0000 | [diff] [blame] | 95 | by \var{iterable}. \var{key}, if provided, specifies a function of one |
| 96 | argument that is used to extract a comparison key from each element |
| 97 | in the iterable: \samp{\var{key}=\function{str.lower}} |
| 98 | Equivalent to: \samp{sorted(iterable, key=key, reverse=True)[:n]} |
| 99 | \versionadded{2.4} |
| 100 | \versionchanged[Added the optional \var{key} argument]{2.5} |
Raymond Hettinger | 33ecffb | 2004-06-10 05:03:17 +0000 | [diff] [blame] | 101 | \end{funcdesc} |
| 102 | |
Raymond Hettinger | 4901a1f | 2004-12-02 08:59:14 +0000 | [diff] [blame] | 103 | \begin{funcdesc}{nsmallest}{n, iterable\optional{, key}} |
Raymond Hettinger | 33ecffb | 2004-06-10 05:03:17 +0000 | [diff] [blame] | 104 | Return a list with the \var{n} smallest elements from the dataset defined |
Raymond Hettinger | 4901a1f | 2004-12-02 08:59:14 +0000 | [diff] [blame] | 105 | by \var{iterable}. \var{key}, if provided, specifies a function of one |
| 106 | argument that is used to extract a comparison key from each element |
| 107 | in the iterable: \samp{\var{key}=\function{str.lower}} |
| 108 | Equivalent to: \samp{sorted(iterable, key=key)[:n]} |
| 109 | \versionadded{2.4} |
| 110 | \versionchanged[Added the optional \var{key} argument]{2.5} |
Raymond Hettinger | 33ecffb | 2004-06-10 05:03:17 +0000 | [diff] [blame] | 111 | \end{funcdesc} |
| 112 | |
Raymond Hettinger | 33ecffb | 2004-06-10 05:03:17 +0000 | [diff] [blame] | 113 | Both functions perform best for smaller values of \var{n}. For larger |
| 114 | values, it is more efficient to use the \function{sorted()} function. Also, |
| 115 | when \code{n==1}, it is more efficient to use the builtin \function{min()} |
| 116 | and \function{max()} functions. |
| 117 | |
Guido van Rossum | 9751216 | 2002-08-02 18:03:24 +0000 | [diff] [blame] | 118 | |
| 119 | \subsection{Theory} |
| 120 | |
| 121 | (This explanation is due to François Pinard. The Python |
| 122 | code for this module was contributed by Kevin O'Connor.) |
| 123 | |
| 124 | Heaps are arrays for which \code{a[\var{k}] <= a[2*\var{k}+1]} and |
| 125 | \code{a[\var{k}] <= a[2*\var{k}+2]} |
| 126 | for all \var{k}, counting elements from 0. For the sake of comparison, |
| 127 | non-existing elements are considered to be infinite. The interesting |
| 128 | property of a heap is that \code{a[0]} is always its smallest element. |
| 129 | |
| 130 | The strange invariant above is meant to be an efficient memory |
| 131 | representation for a tournament. The numbers below are \var{k}, not |
| 132 | \code{a[\var{k}]}: |
| 133 | |
| 134 | \begin{verbatim} |
| 135 | 0 |
| 136 | |
| 137 | 1 2 |
| 138 | |
| 139 | 3 4 5 6 |
| 140 | |
| 141 | 7 8 9 10 11 12 13 14 |
| 142 | |
| 143 | 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
| 144 | \end{verbatim} |
| 145 | |
| 146 | In the tree above, each cell \var{k} is topping \code{2*\var{k}+1} and |
| 147 | \code{2*\var{k}+2}. |
| 148 | In an usual binary tournament we see in sports, each cell is the winner |
| 149 | over the two cells it tops, and we can trace the winner down the tree |
| 150 | to see all opponents s/he had. However, in many computer applications |
| 151 | of such tournaments, we do not need to trace the history of a winner. |
| 152 | To be more memory efficient, when a winner is promoted, we try to |
| 153 | replace it by something else at a lower level, and the rule becomes |
| 154 | that a cell and the two cells it tops contain three different items, |
| 155 | but the top cell "wins" over the two topped cells. |
| 156 | |
| 157 | If this heap invariant is protected at all time, index 0 is clearly |
| 158 | the overall winner. The simplest algorithmic way to remove it and |
| 159 | find the "next" winner is to move some loser (let's say cell 30 in the |
| 160 | diagram above) into the 0 position, and then percolate this new 0 down |
| 161 | the tree, exchanging values, until the invariant is re-established. |
| 162 | This is clearly logarithmic on the total number of items in the tree. |
| 163 | By iterating over all items, you get an O(n log n) sort. |
| 164 | |
| 165 | A nice feature of this sort is that you can efficiently insert new |
| 166 | items while the sort is going on, provided that the inserted items are |
| 167 | not "better" than the last 0'th element you extracted. This is |
| 168 | especially useful in simulation contexts, where the tree holds all |
| 169 | incoming events, and the "win" condition means the smallest scheduled |
| 170 | time. When an event schedule other events for execution, they are |
| 171 | scheduled into the future, so they can easily go into the heap. So, a |
| 172 | heap is a good structure for implementing schedulers (this is what I |
| 173 | used for my MIDI sequencer :-). |
| 174 | |
| 175 | Various structures for implementing schedulers have been extensively |
| 176 | studied, and heaps are good for this, as they are reasonably speedy, |
| 177 | the speed is almost constant, and the worst case is not much different |
| 178 | than the average case. However, there are other representations which |
| 179 | are more efficient overall, yet the worst cases might be terrible. |
| 180 | |
| 181 | Heaps are also very useful in big disk sorts. You most probably all |
| 182 | know that a big sort implies producing "runs" (which are pre-sorted |
| 183 | sequences, which size is usually related to the amount of CPU memory), |
| 184 | followed by a merging passes for these runs, which merging is often |
| 185 | very cleverly organised\footnote{The disk balancing algorithms which |
| 186 | are current, nowadays, are |
| 187 | more annoying than clever, and this is a consequence of the seeking |
| 188 | capabilities of the disks. On devices which cannot seek, like big |
| 189 | tape drives, the story was quite different, and one had to be very |
| 190 | clever to ensure (far in advance) that each tape movement will be the |
| 191 | most effective possible (that is, will best participate at |
| 192 | "progressing" the merge). Some tapes were even able to read |
| 193 | backwards, and this was also used to avoid the rewinding time. |
| 194 | Believe me, real good tape sorts were quite spectacular to watch! |
| 195 | From all times, sorting has always been a Great Art! :-)}. |
| 196 | It is very important that the initial |
| 197 | sort produces the longest runs possible. Tournaments are a good way |
| 198 | to that. If, using all the memory available to hold a tournament, you |
| 199 | replace and percolate items that happen to fit the current run, you'll |
| 200 | produce runs which are twice the size of the memory for random input, |
| 201 | and much better for input fuzzily ordered. |
| 202 | |
| 203 | Moreover, if you output the 0'th item on disk and get an input which |
| 204 | may not fit in the current tournament (because the value "wins" over |
| 205 | the last output value), it cannot fit in the heap, so the size of the |
| 206 | heap decreases. The freed memory could be cleverly reused immediately |
| 207 | for progressively building a second heap, which grows at exactly the |
| 208 | same rate the first heap is melting. When the first heap completely |
| 209 | vanishes, you switch heaps and start a new run. Clever and quite |
| 210 | effective! |
| 211 | |
| 212 | In a word, heaps are useful memory structures to know. I use them in |
| 213 | a few applications, and I think it is good to keep a `heap' module |
| 214 | around. :-) |