Doc/library/heapq.rst

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