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