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