Debian Codegraph @

Doc/library/heapq.rst

raw
1 :mod:`!heapq` --- Heap queue algorithm
2 ======================================
3
4 .. module:: heapq
5 :synopsis: Heap queue algorithm (a.k.a. priority queue).
6
7 .. moduleauthor:: Kevin O'Connor
8 .. sectionauthor:: Guido van Rossum <[email protected]>
9 .. sectionauthor:: François Pinard
10 .. sectionauthor:: Raymond Hettinger
11
12 **Source code:** :source:`Lib/heapq.py`
13
14 --------------
15
16 This module provides an implementation of the heap queue algorithm, also known
17 as the priority queue algorithm.
18
19 Min-heaps are binary trees for which every parent node has a value less than
20 or equal to any of its children.
21 We refer to this condition as the heap invariant.
22
23 For min-heaps, this implementation uses lists for which
24 ``heap[k] <= heap[2*k+1]`` and ``heap[k] <= heap[2*k+2]`` for all *k* for which
25 the compared elements exist. Elements are counted from zero. The interesting
26 property of a min-heap is that its smallest element is always the root,
27 ``heap[0]``.
28
29 Max-heaps satisfy the reverse invariant: every parent node has a value
30 *greater* than any of its children. These are implemented as lists for which
31 ``maxheap[2*k+1] <= maxheap[k]`` and ``maxheap[2*k+2] <= maxheap[k]`` for all
32 *k* for which the compared elements exist.
33 The root, ``maxheap[0]``, contains the *largest* element;
34 ``heap.sort(reverse=True)`` maintains the max-heap invariant.
35
36 The :mod:`!heapq` API differs from textbook heap algorithms in two aspects: (a)
37 We use zero-based indexing. This makes the relationship between the index for
38 a node and the indexes for its children slightly less obvious, but is more
39 suitable since Python uses zero-based indexing. (b) Textbooks often focus on
40 max-heaps, due to their suitability for in-place sorting. Our implementation
41 favors min-heaps as they better correspond to Python :class:`lists <list>`.
42
43 These two aspects make it possible to view the heap as a regular Python list
44 without surprises: ``heap[0]`` is the smallest item, and ``heap.sort()``
45 maintains the heap invariant!
46
47 Like :meth:`list.sort`, this implementation uses only the ``<`` operator
48 for comparisons, for both min-heaps and max-heaps.
49
50 In the API below, and in this documentation, the unqualified term *heap*
51 generally refers to a min-heap.
52 The API for max-heaps is named using a ``_max`` suffix.
53
54 To create a heap, use a list initialized as ``[]``, or transform an existing list
55 into a min-heap or max-heap using the :func:`heapify` or :func:`heapify_max`
56 functions, respectively.
57
58 The following functions are provided for min-heaps:
59
60
61 .. function:: heapify(x)
62
63 Transform list *x* into a min-heap, in-place, in linear time.
64
65
66 .. function:: heappush(heap, item)
67
68 Push the value *item* onto the *heap*, maintaining the min-heap invariant.
69
70
71 .. function:: heappop(heap)
72
73 Pop and return the smallest item from the *heap*, maintaining the min-heap
74 invariant. If the heap is empty, :exc:`IndexError` is raised. To access the
75 smallest item without popping it, use ``heap[0]``.
76
77
78 .. function:: heappushpop(heap, item)
79
80 Push *item* on the heap, then pop and return the smallest item from the
81 *heap*. The combined action runs more efficiently than :func:`heappush`
82 followed by a separate call to :func:`heappop`.
83
84
85 .. function:: heapreplace(heap, item)
86
87 Pop and return the smallest item from the *heap*, and also push the new *item*.
88 The heap size doesn't change. If the heap is empty, :exc:`IndexError` is raised.
89
90 This one step operation is more efficient than a :func:`heappop` followed by
91 :func:`heappush` and can be more appropriate when using a fixed-size heap.
92 The pop/push combination always returns an element from the heap and replaces
93 it with *item*.
94
95 The value returned may be larger than the *item* added. If that isn't
96 desired, consider using :func:`heappushpop` instead. Its push/pop
97 combination returns the smaller of the two values, leaving the larger value
98 on the heap.
99
100
101 For max-heaps, the following functions are provided:
102
103
104 .. function:: heapify_max(x)
105
106 Transform list *x* into a max-heap, in-place, in linear time.
107
108 .. versionadded:: 3.14
109
110
111 .. function:: heappush_max(heap, item)
112
113 Push the value *item* onto the max-heap *heap*, maintaining the max-heap
114 invariant.
115
116 .. versionadded:: 3.14
117
118
119 .. function:: heappop_max(heap)
120
121 Pop and return the largest item from the max-heap *heap*, maintaining the
122 max-heap invariant. If the max-heap is empty, :exc:`IndexError` is raised.
123 To access the largest item without popping it, use ``maxheap[0]``.
124
125 .. versionadded:: 3.14
126
127
128 .. function:: heappushpop_max(heap, item)
129
130 Push *item* on the max-heap *heap*, then pop and return the largest item
131 from *heap*.
132 The combined action runs more efficiently than :func:`heappush_max`
133 followed by a separate call to :func:`heappop_max`.
134
135 .. versionadded:: 3.14
136
137
138 .. function:: heapreplace_max(heap, item)
139
140 Pop and return the largest item from the max-heap *heap* and also push the
141 new *item*.
142 The max-heap size doesn't change. If the max-heap is empty,
143 :exc:`IndexError` is raised.
144
145 The value returned may be smaller than the *item* added. Refer to the
146 analogous function :func:`heapreplace` for detailed usage notes.
147
148 .. versionadded:: 3.14
149
150
151 The module also offers three general purpose functions based on heaps.
152
153
154 .. function:: merge(*iterables, key=None, reverse=False)
155
156 Merge multiple sorted inputs into a single sorted output (for example, merge
157 timestamped entries from multiple log files). Returns an :term:`iterator`
158 over the sorted values.
159
160 Similar to ``sorted(itertools.chain(*iterables))`` but returns an iterable, does
161 not pull the data into memory all at once, and assumes that each of the input
162 streams is already sorted (smallest to largest).
163
164 Has two optional arguments which must be specified as keyword arguments.
165
166 *key* specifies a :term:`key function` of one argument that is used to
167 extract a comparison key from each input element. The default value is
168 ``None`` (compare the elements directly).
169
170 *reverse* is a boolean value. If set to ``True``, then the input elements
171 are merged as if each comparison were reversed. To achieve behavior similar
172 to ``sorted(itertools.chain(*iterables), reverse=True)``, all iterables must
173 be sorted from largest to smallest.
174
175 .. versionchanged:: 3.5
176 Added the optional *key* and *reverse* parameters.
177
178
179 .. function:: nlargest(n, iterable, key=None)
180
181 Return a list with the *n* largest elements from the dataset defined by
182 *iterable*. *key*, if provided, specifies a function of one argument that is
183 used to extract a comparison key from each element in *iterable* (for example,
184 ``key=str.lower``). Equivalent to: ``sorted(iterable, key=key,
185 reverse=True)[:n]``.
186
187
188 .. function:: nsmallest(n, iterable, key=None)
189
190 Return a list with the *n* smallest elements from the dataset defined by
191 *iterable*. *key*, if provided, specifies a function of one argument that is
192 used to extract a comparison key from each element in *iterable* (for example,
193 ``key=str.lower``). Equivalent to: ``sorted(iterable, key=key)[:n]``.
194
195
196 The latter two functions perform best for smaller values of *n*. For larger
197 values, it is more efficient to use the :func:`sorted` function. Also, when
198 ``n==1``, it is more efficient to use the built-in :func:`min` and :func:`max`
199 functions. If repeated usage of these functions is required, consider turning
200 the iterable into an actual heap.
201
202
203 Basic Examples
204 --------------
205
206 A `heapsort <https://en.wikipedia.org/wiki/Heapsort>`_ can be implemented by
207 pushing all values onto a heap and then popping off the smallest values one at a
208 time::
209
210 >>> def heapsort(iterable):
211 ... h = []
212 ... for value in iterable:
213 ... heappush(h, value)
214 ... return [heappop(h) for i in range(len(h))]
215 ...
216 >>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
217 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
218
219 This is similar to ``sorted(iterable)``, but unlike :func:`sorted`, this
220 implementation is not stable.
221
222 Heap elements can be tuples. This is useful for assigning comparison values
223 (such as task priorities) alongside the main record being tracked::
224
225 >>> h = []
226 >>> heappush(h, (5, 'write code'))
227 >>> heappush(h, (7, 'release product'))
228 >>> heappush(h, (1, 'write spec'))
229 >>> heappush(h, (3, 'create tests'))
230 >>> heappop(h)
231 (1, 'write spec')
232
233
234 Other Applications
235 ------------------
236
237 `Medians <https://en.wikipedia.org/wiki/Median>`_ are a measure of
238 central tendency for a set of numbers. In distributions skewed by
239 outliers, the median provides a more stable estimate than an average
240 (arithmetic mean). A running median is an `online algorithm
241 <https://en.wikipedia.org/wiki/Online_algorithm>`_ that updates
242 continuously as new data arrives.
243
244 A running median can be efficiently implemented by balancing two heaps,
245 a max-heap for values at or below the midpoint and a min-heap for values
246 above the midpoint. When the two heaps have the same size, the new
247 median is the average of the tops of the two heaps; otherwise, the
248 median is at the top of the larger heap::
249
250 def running_median(iterable):
251 "Yields the cumulative median of values seen so far."
252
253 lo = [] # max-heap
254 hi = [] # min-heap (same size as or one smaller than lo)
255
256 for x in iterable:
257 if len(lo) == len(hi):
258 heappush_max(lo, heappushpop(hi, x))
259 yield lo[0]
260 else:
261 heappush(hi, heappushpop_max(lo, x))
262 yield (lo[0] + hi[0]) / 2
263
264 For example::
265
266 >>> list(running_median([5.0, 9.0, 4.0, 12.0, 8.0, 9.0]))
267 [5.0, 7.0, 5.0, 7.0, 8.0, 8.5]
268
269
270 Priority Queue Implementation Notes
271 -----------------------------------
272
273 A `priority queue <https://en.wikipedia.org/wiki/Priority_queue>`_ is common use
274 for a heap, and it presents several implementation challenges:
275
276 * Sort stability: how do you get two tasks with equal priorities to be returned
277 in the order they were originally added?
278
279 * Tuple comparison breaks for (priority, task) pairs if the priorities are equal
280 and the tasks do not have a default comparison order.
281
282 * If the priority of a task changes, how do you move it to a new position in
283 the heap?
284
285 * Or if a pending task needs to be deleted, how do you find it and remove it
286 from the queue?
287
288 A solution to the first two challenges is to store entries as 3-element list
289 including the priority, an entry count, and the task. The entry count serves as
290 a tie-breaker so that two tasks with the same priority are returned in the order
291 they were added. And since no two entry counts are the same, the tuple
292 comparison will never attempt to directly compare two tasks.
293
294 Another solution to the problem of non-comparable tasks is to create a wrapper
295 class that ignores the task item and only compares the priority field::
296
297 from dataclasses import dataclass, field
298 from typing import Any
299
300 @dataclass(order=True)
301 class PrioritizedItem:
302 priority: int
303 item: Any=field(compare=False)
304
305 The remaining challenges revolve around finding a pending task and making
306 changes to its priority or removing it entirely. Finding a task can be done
307 with a dictionary pointing to an entry in the queue.
308
309 Removing the entry or changing its priority is more difficult because it would
310 break the heap structure invariants. So, a possible solution is to mark the
311 entry as removed and add a new entry with the revised priority::
312
313 pq = [] # list of entries arranged in a heap
314 entry_finder = {} # mapping of tasks to entries
315 REMOVED = '<removed-task>' # placeholder for a removed task
316 counter = itertools.count() # unique sequence count
317
318 def add_task(task, priority=0):
319 'Add a new task or update the priority of an existing task'
320 if task in entry_finder:
321 remove_task(task)
322 count = next(counter)
323 entry = [priority, count, task]
324 entry_finder[task] = entry
325 heappush(pq, entry)
326
327 def remove_task(task):
328 'Mark an existing task as REMOVED. Raise KeyError if not found.'
329 entry = entry_finder.pop(task)
330 entry[-1] = REMOVED
331
332 def pop_task():
333 'Remove and return the lowest priority task. Raise KeyError if empty.'
334 while pq:
335 priority, count, task = heappop(pq)
336 if task is not REMOVED:
337 del entry_finder[task]
338 return task
339 raise KeyError('pop from an empty priority queue')
340
341
342 Theory
343 ------
344
345 Heaps are arrays for which ``a[k] <= a[2*k+1]`` and ``a[k] <= a[2*k+2]`` for all
346 *k*, counting elements from 0. For the sake of comparison, non-existing
347 elements are considered to be infinite. The interesting property of a heap is
348 that ``a[0]`` is always its smallest element.
349
350 The strange invariant above is meant to be an efficient memory representation
351 for a tournament. The numbers below are *k*, not ``a[k]``::
352
353 0
354
355 1 2
356
357 3 4 5 6
358
359 7 8 9 10 11 12 13 14
360
361 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
362
363 In the tree above, each cell *k* is topping ``2*k+1`` and ``2*k+2``. In a usual
364 binary tournament we see in sports, each cell is the winner over the two cells
365 it tops, and we can trace the winner down the tree to see all opponents s/he
366 had. However, in many computer applications of such tournaments, we do not need
367 to trace the history of a winner. To be more memory efficient, when a winner is
368 promoted, we try to replace it by something else at a lower level, and the rule
369 becomes that a cell and the two cells it tops contain three different items, but
370 the top cell "wins" over the two topped cells.
371
372 If this heap invariant is protected at all time, index 0 is clearly the overall
373 winner. The simplest algorithmic way to remove it and find the "next" winner is
374 to move some loser (let's say cell 30 in the diagram above) into the 0 position,
375 and then percolate this new 0 down the tree, exchanging values, until the
376 invariant is re-established. This is clearly logarithmic on the total number of
377 items in the tree. By iterating over all items, you get an *O*\ (*n* log *n*) sort.
378
379 A nice feature of this sort is that you can efficiently insert new items while
380 the sort is going on, provided that the inserted items are not "better" than the
381 last 0'th element you extracted. This is especially useful in simulation
382 contexts, where the tree holds all incoming events, and the "win" condition
383 means the smallest scheduled time. When an event schedules other events for
384 execution, they are scheduled into the future, so they can easily go into the
385 heap. So, a heap is a good structure for implementing schedulers (this is what
386 I used for my MIDI sequencer :-).
387
388 Various structures for implementing schedulers have been extensively studied,
389 and heaps are good for this, as they are reasonably speedy, the speed is almost
390 constant, and the worst case is not much different than the average case.
391 However, there are other representations which are more efficient overall, yet
392 the worst cases might be terrible.
393
394 Heaps are also very useful in big disk sorts. You most probably all know that a
395 big sort implies producing "runs" (which are pre-sorted sequences, whose size is
396 usually related to the amount of CPU memory), followed by a merging passes for
397 these runs, which merging is often very cleverly organised [#]_. It is very
398 important that the initial sort produces the longest runs possible. Tournaments
399 are a good way to achieve that. If, using all the memory available to hold a
400 tournament, you replace and percolate items that happen to fit the current run,
401 you'll produce runs which are twice the size of the memory for random input, and
402 much better for input fuzzily ordered.
403
404 Moreover, if you output the 0'th item on disk and get an input which may not fit
405 in the current tournament (because the value "wins" over the last output value),
406 it cannot fit in the heap, so the size of the heap decreases. The freed memory
407 could be cleverly reused immediately for progressively building a second heap,
408 which grows at exactly the same rate the first heap is melting. When the first
409 heap completely vanishes, you switch heaps and start a new run. Clever and
410 quite effective!
411
412 In a word, heaps are useful memory structures to know. I use them in a few
413 applications, and I think it is good to keep a 'heap' module around. :-)
414
415 .. rubric:: Footnotes
416
417 .. [#] The disk balancing algorithms which are current, nowadays, are more annoying
418 than clever, and this is a consequence of the seeking capabilities of the disks.
419 On devices which cannot seek, like big tape drives, the story was quite
420 different, and one had to be very clever to ensure (far in advance) that each
421 tape movement will be the most effective possible (that is, will best
422 participate at "progressing" the merge). Some tapes were even able to read
423 backwards, and this was also used to avoid the rewinding time. Believe me, real
424 good tape sorts were quite spectacular to watch! From all times, sorting has
425 always been a Great Art! :-)