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