Branch data Line data Source code
1 : : /* Drop in replacement for heapq.py
2 : :
3 : : C implementation derived directly from heapq.py in Py2.3
4 : : which was written by Kevin O'Connor, augmented by Tim Peters,
5 : : annotated by François Pinard, and converted to C by Raymond Hettinger.
6 : :
7 : : */
8 : :
9 : : #ifndef Py_BUILD_CORE_BUILTIN
10 : : # define Py_BUILD_CORE_MODULE 1
11 : : #endif
12 : :
13 : : #include "Python.h"
14 : : #include "pycore_list.h" // _PyList_ITEMS()
15 : :
16 : : #include "clinic/_heapqmodule.c.h"
17 : :
18 : :
19 : : /*[clinic input]
20 : : module _heapq
21 : : [clinic start generated code]*/
22 : : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=d7cca0a2e4c0ceb3]*/
23 : :
24 : : static int
25 : 73040 : siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
26 : : {
27 : : PyObject *newitem, *parent, **arr;
28 : : Py_ssize_t parentpos, size;
29 : : int cmp;
30 : :
31 : : assert(PyList_Check(heap));
32 : 73040 : size = PyList_GET_SIZE(heap);
33 [ - + ]: 73040 : if (pos >= size) {
34 : 0 : PyErr_SetString(PyExc_IndexError, "index out of range");
35 : 0 : return -1;
36 : : }
37 : :
38 : : /* Follow the path to the root, moving parents down until finding
39 : : a place newitem fits. */
40 : 73040 : arr = _PyList_ITEMS(heap);
41 : 73040 : newitem = arr[pos];
42 [ + + ]: 123619 : while (pos > startpos) {
43 : 99596 : parentpos = (pos - 1) >> 1;
44 : 99596 : parent = arr[parentpos];
45 : 99596 : Py_INCREF(newitem);
46 : 99596 : Py_INCREF(parent);
47 : 99596 : cmp = PyObject_RichCompareBool(newitem, parent, Py_LT);
48 : 99596 : Py_DECREF(parent);
49 : 99596 : Py_DECREF(newitem);
50 [ + + ]: 99596 : if (cmp < 0)
51 : 3 : return -1;
52 [ + + ]: 99593 : if (size != PyList_GET_SIZE(heap)) {
53 : 3 : PyErr_SetString(PyExc_RuntimeError,
54 : : "list changed size during iteration");
55 : 3 : return -1;
56 : : }
57 [ + + ]: 99590 : if (cmp == 0)
58 : 49011 : break;
59 : 50579 : arr = _PyList_ITEMS(heap);
60 : 50579 : parent = arr[parentpos];
61 : 50579 : newitem = arr[pos];
62 : 50579 : arr[parentpos] = newitem;
63 : 50579 : arr[pos] = parent;
64 : 50579 : pos = parentpos;
65 : : }
66 : 73034 : return 0;
67 : : }
68 : :
69 : : static int
70 : 60251 : siftup(PyListObject *heap, Py_ssize_t pos)
71 : : {
72 : : Py_ssize_t startpos, endpos, childpos, limit;
73 : : PyObject *tmp1, *tmp2, **arr;
74 : : int cmp;
75 : :
76 : : assert(PyList_Check(heap));
77 : 60251 : endpos = PyList_GET_SIZE(heap);
78 : 60251 : startpos = pos;
79 [ - + ]: 60251 : if (pos >= endpos) {
80 : 0 : PyErr_SetString(PyExc_IndexError, "index out of range");
81 : 0 : return -1;
82 : : }
83 : :
84 : : /* Bubble up the smaller child until hitting a leaf. */
85 : 60251 : arr = _PyList_ITEMS(heap);
86 : 60251 : limit = endpos >> 1; /* smallest pos that has no child */
87 [ + + ]: 203995 : while (pos < limit) {
88 : : /* Set childpos to index of smaller child. */
89 : 143747 : childpos = 2*pos + 1; /* leftmost child position */
90 [ + + ]: 143747 : if (childpos + 1 < endpos) {
91 : 117988 : PyObject* a = arr[childpos];
92 : 117988 : PyObject* b = arr[childpos + 1];
93 : 117988 : Py_INCREF(a);
94 : 117988 : Py_INCREF(b);
95 : 117988 : cmp = PyObject_RichCompareBool(a, b, Py_LT);
96 : 117988 : Py_DECREF(a);
97 : 117988 : Py_DECREF(b);
98 [ + + ]: 117988 : if (cmp < 0)
99 : 2 : return -1;
100 : 117986 : childpos += ((unsigned)cmp ^ 1); /* increment when cmp==0 */
101 : 117986 : arr = _PyList_ITEMS(heap); /* arr may have changed */
102 [ + + ]: 117986 : if (endpos != PyList_GET_SIZE(heap)) {
103 : 1 : PyErr_SetString(PyExc_RuntimeError,
104 : : "list changed size during iteration");
105 : 1 : return -1;
106 : : }
107 : : }
108 : : /* Move the smaller child up. */
109 : 143744 : tmp1 = arr[childpos];
110 : 143744 : tmp2 = arr[pos];
111 : 143744 : arr[childpos] = tmp2;
112 : 143744 : arr[pos] = tmp1;
113 : 143744 : pos = childpos;
114 : : }
115 : : /* Bubble it up to its final resting place (by sifting its parents down). */
116 : 60248 : return siftdown(heap, startpos, pos);
117 : : }
118 : :
119 : : /*[clinic input]
120 : : _heapq.heappush
121 : :
122 : : heap: object(subclass_of='&PyList_Type')
123 : : item: object
124 : : /
125 : :
126 : : Push item onto heap, maintaining the heap invariant.
127 : : [clinic start generated code]*/
128 : :
129 : : static PyObject *
130 : 12792 : _heapq_heappush_impl(PyObject *module, PyObject *heap, PyObject *item)
131 : : /*[clinic end generated code: output=912c094f47663935 input=7c69611f3698aceb]*/
132 : : {
133 [ - + ]: 12792 : if (PyList_Append(heap, item))
134 : 0 : return NULL;
135 : :
136 [ + + ]: 12792 : if (siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1))
137 : 4 : return NULL;
138 : 12788 : Py_RETURN_NONE;
139 : : }
140 : :
141 : : static PyObject *
142 : 14020 : heappop_internal(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t))
143 : : {
144 : : PyObject *lastelt, *returnitem;
145 : : Py_ssize_t n;
146 : :
147 : : /* raises IndexError if the heap is empty */
148 : 14020 : n = PyList_GET_SIZE(heap);
149 [ + + ]: 14020 : if (n == 0) {
150 : 2 : PyErr_SetString(PyExc_IndexError, "index out of range");
151 : 2 : return NULL;
152 : : }
153 : :
154 : 14018 : lastelt = PyList_GET_ITEM(heap, n-1) ;
155 : 14018 : Py_INCREF(lastelt);
156 [ - + ]: 14018 : if (PyList_SetSlice(heap, n-1, n, NULL)) {
157 : 0 : Py_DECREF(lastelt);
158 : 0 : return NULL;
159 : : }
160 : 14018 : n--;
161 : :
162 [ + + ]: 14018 : if (!n)
163 : 921 : return lastelt;
164 : 13097 : returnitem = PyList_GET_ITEM(heap, 0);
165 : 13097 : PyList_SET_ITEM(heap, 0, lastelt);
166 [ + + ]: 13097 : if (siftup_func((PyListObject *)heap, 0)) {
167 : 2 : Py_DECREF(returnitem);
168 : 2 : return NULL;
169 : : }
170 : 13095 : return returnitem;
171 : : }
172 : :
173 : : /*[clinic input]
174 : : _heapq.heappop
175 : :
176 : : heap: object(subclass_of='&PyList_Type')
177 : : /
178 : :
179 : : Pop the smallest item off the heap, maintaining the heap invariant.
180 : : [clinic start generated code]*/
181 : :
182 : : static PyObject *
183 : 14018 : _heapq_heappop_impl(PyObject *module, PyObject *heap)
184 : : /*[clinic end generated code: output=96dfe82d37d9af76 input=91487987a583c856]*/
185 : : {
186 : 14018 : return heappop_internal(heap, siftup);
187 : : }
188 : :
189 : : static PyObject *
190 : 35714 : heapreplace_internal(PyObject *heap, PyObject *item, int siftup_func(PyListObject *, Py_ssize_t))
191 : : {
192 : : PyObject *returnitem;
193 : :
194 [ + + ]: 35714 : if (PyList_GET_SIZE(heap) == 0) {
195 : 1 : PyErr_SetString(PyExc_IndexError, "index out of range");
196 : 1 : return NULL;
197 : : }
198 : :
199 : 35713 : returnitem = PyList_GET_ITEM(heap, 0);
200 : 35713 : Py_INCREF(item);
201 : 35713 : PyList_SET_ITEM(heap, 0, item);
202 [ + + ]: 35713 : if (siftup_func((PyListObject *)heap, 0)) {
203 : 1 : Py_DECREF(returnitem);
204 : 1 : return NULL;
205 : : }
206 : 35712 : return returnitem;
207 : : }
208 : :
209 : :
210 : : /*[clinic input]
211 : : _heapq.heapreplace
212 : :
213 : : heap: object(subclass_of='&PyList_Type')
214 : : item: object
215 : : /
216 : :
217 : : Pop and return the current smallest value, and add the new item.
218 : :
219 : : This is more efficient than heappop() followed by heappush(), and can be
220 : : more appropriate when using a fixed-size heap. Note that the value
221 : : returned may be larger than item! That constrains reasonable uses of
222 : : this routine unless written as part of a conditional replacement:
223 : :
224 : : if item > heap[0]:
225 : : item = heapreplace(heap, item)
226 : : [clinic start generated code]*/
227 : :
228 : : static PyObject *
229 : 33124 : _heapq_heapreplace_impl(PyObject *module, PyObject *heap, PyObject *item)
230 : : /*[clinic end generated code: output=82ea55be8fbe24b4 input=719202ac02ba10c8]*/
231 : : {
232 : 33124 : return heapreplace_internal(heap, item, siftup);
233 : : }
234 : :
235 : : /*[clinic input]
236 : : _heapq.heappushpop
237 : :
238 : : heap: object(subclass_of='&PyList_Type')
239 : : item: object
240 : : /
241 : :
242 : : Push item on the heap, then pop and return the smallest item from the heap.
243 : :
244 : : The combined action runs more efficiently than heappush() followed by
245 : : a separate call to heappop().
246 : : [clinic start generated code]*/
247 : :
248 : : static PyObject *
249 : 996 : _heapq_heappushpop_impl(PyObject *module, PyObject *heap, PyObject *item)
250 : : /*[clinic end generated code: output=67231dc98ed5774f input=5dc701f1eb4a4aa7]*/
251 : : {
252 : : PyObject *returnitem;
253 : : int cmp;
254 : :
255 [ + + ]: 996 : if (PyList_GET_SIZE(heap) == 0) {
256 : 2 : Py_INCREF(item);
257 : 2 : return item;
258 : : }
259 : :
260 : 994 : PyObject* top = PyList_GET_ITEM(heap, 0);
261 : 994 : Py_INCREF(top);
262 : 994 : cmp = PyObject_RichCompareBool(top, item, Py_LT);
263 : 994 : Py_DECREF(top);
264 [ - + ]: 994 : if (cmp < 0)
265 : 0 : return NULL;
266 [ + + ]: 994 : if (cmp == 0) {
267 : 948 : Py_INCREF(item);
268 : 948 : return item;
269 : : }
270 : :
271 [ + + ]: 46 : if (PyList_GET_SIZE(heap) == 0) {
272 : 1 : PyErr_SetString(PyExc_IndexError, "index out of range");
273 : 1 : return NULL;
274 : : }
275 : :
276 : 45 : returnitem = PyList_GET_ITEM(heap, 0);
277 : 45 : Py_INCREF(item);
278 : 45 : PyList_SET_ITEM(heap, 0, item);
279 [ - + ]: 45 : if (siftup((PyListObject *)heap, 0)) {
280 : 0 : Py_DECREF(returnitem);
281 : 0 : return NULL;
282 : : }
283 : 45 : return returnitem;
284 : : }
285 : :
286 : : static Py_ssize_t
287 : 1 : keep_top_bit(Py_ssize_t n)
288 : : {
289 : 1 : int i = 0;
290 : :
291 [ + + ]: 14 : while (n > 1) {
292 : 13 : n >>= 1;
293 : 13 : i++;
294 : : }
295 : 1 : return n << i;
296 : : }
297 : :
298 : : /* Cache friendly version of heapify()
299 : : -----------------------------------
300 : :
301 : : Build-up a heap in O(n) time by performing siftup() operations
302 : : on nodes whose children are already heaps.
303 : :
304 : : The simplest way is to sift the nodes in reverse order from
305 : : n//2-1 to 0 inclusive. The downside is that children may be
306 : : out of cache by the time their parent is reached.
307 : :
308 : : A better way is to not wait for the children to go out of cache.
309 : : Once a sibling pair of child nodes have been sifted, immediately
310 : : sift their parent node (while the children are still in cache).
311 : :
312 : : Both ways build child heaps before their parents, so both ways
313 : : do the exact same number of comparisons and produce exactly
314 : : the same heap. The only difference is that the traversal
315 : : order is optimized for cache efficiency.
316 : : */
317 : :
318 : : static PyObject *
319 : 1 : cache_friendly_heapify(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t))
320 : : {
321 : : Py_ssize_t i, j, m, mhalf, leftmost;
322 : :
323 : 1 : m = PyList_GET_SIZE(heap) >> 1; /* index of first childless node */
324 : 1 : leftmost = keep_top_bit(m + 1) - 1; /* leftmost node in row of m */
325 : 1 : mhalf = m >> 1; /* parent of first childless node */
326 : :
327 [ + + ]: 3192 : for (i = leftmost - 1 ; i >= mhalf ; i--) {
328 : 3191 : j = i;
329 : : while (1) {
330 [ - + ]: 6374 : if (siftup_func((PyListObject *)heap, j))
331 : 0 : return NULL;
332 [ + + ]: 6374 : if (!(j & 1))
333 : 3191 : break;
334 : 3183 : j >>= 1;
335 : : }
336 : : }
337 : :
338 [ + + ]: 1810 : for (i = m - 1 ; i >= leftmost ; i--) {
339 : 1809 : j = i;
340 : : while (1) {
341 [ - + ]: 3626 : if (siftup_func((PyListObject *)heap, j))
342 : 0 : return NULL;
343 [ + + ]: 3626 : if (!(j & 1))
344 : 1809 : break;
345 : 1817 : j >>= 1;
346 : : }
347 : : }
348 : 1 : Py_RETURN_NONE;
349 : : }
350 : :
351 : : static PyObject *
352 : 228 : heapify_internal(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t))
353 : : {
354 : : Py_ssize_t i, n;
355 : :
356 : : /* For heaps likely to be bigger than L1 cache, we use the cache
357 : : friendly heapify function. For smaller heaps that fit entirely
358 : : in cache, we prefer the simpler algorithm with less branching.
359 : : */
360 : 228 : n = PyList_GET_SIZE(heap);
361 [ + + ]: 228 : if (n > 2500)
362 : 1 : return cache_friendly_heapify(heap, siftup_func);
363 : :
364 : : /* Transform bottom-up. The largest index there's any point to
365 : : looking at is the largest with a child index in-range, so must
366 : : have 2*i + 1 < n, or i < (n-1)/2. If n is even = 2*j, this is
367 : : (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If
368 : : n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,
369 : : and that's again n//2-1.
370 : : */
371 [ + + ]: 7267 : for (i = (n >> 1) - 1 ; i >= 0 ; i--)
372 [ + + ]: 7043 : if (siftup_func((PyListObject *)heap, i))
373 : 3 : return NULL;
374 : 224 : Py_RETURN_NONE;
375 : : }
376 : :
377 : : /*[clinic input]
378 : : _heapq.heapify
379 : :
380 : : heap: object(subclass_of='&PyList_Type')
381 : : /
382 : :
383 : : Transform list into a heap, in-place, in O(len(heap)) time.
384 : : [clinic start generated code]*/
385 : :
386 : : static PyObject *
387 : 168 : _heapq_heapify_impl(PyObject *module, PyObject *heap)
388 : : /*[clinic end generated code: output=e63a636fcf83d6d0 input=53bb7a2166febb73]*/
389 : : {
390 : 168 : return heapify_internal(heap, siftup);
391 : : }
392 : :
393 : : static int
394 : 5647 : siftdown_max(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
395 : : {
396 : : PyObject *newitem, *parent, **arr;
397 : : Py_ssize_t parentpos, size;
398 : : int cmp;
399 : :
400 : : assert(PyList_Check(heap));
401 : 5647 : size = PyList_GET_SIZE(heap);
402 [ - + ]: 5647 : if (pos >= size) {
403 : 0 : PyErr_SetString(PyExc_IndexError, "index out of range");
404 : 0 : return -1;
405 : : }
406 : :
407 : : /* Follow the path to the root, moving parents down until finding
408 : : a place newitem fits. */
409 : 5647 : arr = _PyList_ITEMS(heap);
410 : 5647 : newitem = arr[pos];
411 [ + + ]: 9973 : while (pos > startpos) {
412 : 9234 : parentpos = (pos - 1) >> 1;
413 : 9234 : parent = arr[parentpos];
414 : 9234 : Py_INCREF(parent);
415 : 9234 : Py_INCREF(newitem);
416 : 9234 : cmp = PyObject_RichCompareBool(parent, newitem, Py_LT);
417 : 9234 : Py_DECREF(parent);
418 : 9234 : Py_DECREF(newitem);
419 [ + + ]: 9234 : if (cmp < 0)
420 : 1 : return -1;
421 [ - + ]: 9233 : if (size != PyList_GET_SIZE(heap)) {
422 : 0 : PyErr_SetString(PyExc_RuntimeError,
423 : : "list changed size during iteration");
424 : 0 : return -1;
425 : : }
426 [ + + ]: 9233 : if (cmp == 0)
427 : 4907 : break;
428 : 4326 : arr = _PyList_ITEMS(heap);
429 : 4326 : parent = arr[parentpos];
430 : 4326 : newitem = arr[pos];
431 : 4326 : arr[parentpos] = newitem;
432 : 4326 : arr[pos] = parent;
433 : 4326 : pos = parentpos;
434 : : }
435 : 5646 : return 0;
436 : : }
437 : :
438 : : static int
439 : 5647 : siftup_max(PyListObject *heap, Py_ssize_t pos)
440 : : {
441 : : Py_ssize_t startpos, endpos, childpos, limit;
442 : : PyObject *tmp1, *tmp2, **arr;
443 : : int cmp;
444 : :
445 : : assert(PyList_Check(heap));
446 : 5647 : endpos = PyList_GET_SIZE(heap);
447 : 5647 : startpos = pos;
448 [ - + ]: 5647 : if (pos >= endpos) {
449 : 0 : PyErr_SetString(PyExc_IndexError, "index out of range");
450 : 0 : return -1;
451 : : }
452 : :
453 : : /* Bubble up the smaller child until hitting a leaf. */
454 : 5647 : arr = _PyList_ITEMS(heap);
455 : 5647 : limit = endpos >> 1; /* smallest pos that has no child */
456 [ + + ]: 28518 : while (pos < limit) {
457 : : /* Set childpos to index of smaller child. */
458 : 22871 : childpos = 2*pos + 1; /* leftmost child position */
459 [ + + ]: 22871 : if (childpos + 1 < endpos) {
460 : 22705 : PyObject* a = arr[childpos + 1];
461 : 22705 : PyObject* b = arr[childpos];
462 : 22705 : Py_INCREF(a);
463 : 22705 : Py_INCREF(b);
464 : 22705 : cmp = PyObject_RichCompareBool(a, b, Py_LT);
465 : 22705 : Py_DECREF(a);
466 : 22705 : Py_DECREF(b);
467 [ - + ]: 22705 : if (cmp < 0)
468 : 0 : return -1;
469 : 22705 : childpos += ((unsigned)cmp ^ 1); /* increment when cmp==0 */
470 : 22705 : arr = _PyList_ITEMS(heap); /* arr may have changed */
471 [ - + ]: 22705 : if (endpos != PyList_GET_SIZE(heap)) {
472 : 0 : PyErr_SetString(PyExc_RuntimeError,
473 : : "list changed size during iteration");
474 : 0 : return -1;
475 : : }
476 : : }
477 : : /* Move the smaller child up. */
478 : 22871 : tmp1 = arr[childpos];
479 : 22871 : tmp2 = arr[pos];
480 : 22871 : arr[childpos] = tmp2;
481 : 22871 : arr[pos] = tmp1;
482 : 22871 : pos = childpos;
483 : : }
484 : : /* Bubble it up to its final resting place (by sifting its parents down). */
485 : 5647 : return siftdown_max(heap, startpos, pos);
486 : : }
487 : :
488 : :
489 : : /*[clinic input]
490 : : _heapq._heappop_max
491 : :
492 : : heap: object(subclass_of='&PyList_Type')
493 : : /
494 : :
495 : : Maxheap variant of heappop.
496 : : [clinic start generated code]*/
497 : :
498 : : static PyObject *
499 : 2 : _heapq__heappop_max_impl(PyObject *module, PyObject *heap)
500 : : /*[clinic end generated code: output=9e77aadd4e6a8760 input=362c06e1c7484793]*/
501 : : {
502 : 2 : return heappop_internal(heap, siftup_max);
503 : : }
504 : :
505 : : /*[clinic input]
506 : : _heapq._heapreplace_max
507 : :
508 : : heap: object(subclass_of='&PyList_Type')
509 : : item: object
510 : : /
511 : :
512 : : Maxheap variant of heapreplace.
513 : : [clinic start generated code]*/
514 : :
515 : : static PyObject *
516 : 2590 : _heapq__heapreplace_max_impl(PyObject *module, PyObject *heap,
517 : : PyObject *item)
518 : : /*[clinic end generated code: output=8ad7545e4a5e8adb input=f2dd27cbadb948d7]*/
519 : : {
520 : 2590 : return heapreplace_internal(heap, item, siftup_max);
521 : : }
522 : :
523 : : /*[clinic input]
524 : : _heapq._heapify_max
525 : :
526 : : heap: object(subclass_of='&PyList_Type')
527 : : /
528 : :
529 : : Maxheap variant of heapify.
530 : : [clinic start generated code]*/
531 : :
532 : : static PyObject *
533 : 60 : _heapq__heapify_max_impl(PyObject *module, PyObject *heap)
534 : : /*[clinic end generated code: output=2cb028beb4a8b65e input=c1f765ee69f124b8]*/
535 : : {
536 : 60 : return heapify_internal(heap, siftup_max);
537 : : }
538 : :
539 : : static PyMethodDef heapq_methods[] = {
540 : : _HEAPQ_HEAPPUSH_METHODDEF
541 : : _HEAPQ_HEAPPUSHPOP_METHODDEF
542 : : _HEAPQ_HEAPPOP_METHODDEF
543 : : _HEAPQ_HEAPREPLACE_METHODDEF
544 : : _HEAPQ_HEAPIFY_METHODDEF
545 : : _HEAPQ__HEAPPOP_MAX_METHODDEF
546 : : _HEAPQ__HEAPIFY_MAX_METHODDEF
547 : : _HEAPQ__HEAPREPLACE_MAX_METHODDEF
548 : : {NULL, NULL} /* sentinel */
549 : : };
550 : :
551 : : PyDoc_STRVAR(module_doc,
552 : : "Heap queue algorithm (a.k.a. priority queue).\n\
553 : : \n\
554 : : Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
555 : : all k, counting elements from 0. For the sake of comparison,\n\
556 : : non-existing elements are considered to be infinite. The interesting\n\
557 : : property of a heap is that a[0] is always its smallest element.\n\
558 : : \n\
559 : : Usage:\n\
560 : : \n\
561 : : heap = [] # creates an empty heap\n\
562 : : heappush(heap, item) # pushes a new item on the heap\n\
563 : : item = heappop(heap) # pops the smallest item from the heap\n\
564 : : item = heap[0] # smallest item on the heap without popping it\n\
565 : : heapify(x) # transforms list into a heap, in-place, in linear time\n\
566 : : item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\
567 : : # new item; the heap size is unchanged\n\
568 : : \n\
569 : : Our API differs from textbook heap algorithms as follows:\n\
570 : : \n\
571 : : - We use 0-based indexing. This makes the relationship between the\n\
572 : : index for a node and the indexes for its children slightly less\n\
573 : : obvious, but is more suitable since Python uses 0-based indexing.\n\
574 : : \n\
575 : : - Our heappop() method returns the smallest item, not the largest.\n\
576 : : \n\
577 : : These two make it possible to view the heap as a regular Python list\n\
578 : : without surprises: heap[0] is the smallest item, and heap.sort()\n\
579 : : maintains the heap invariant!\n");
580 : :
581 : :
582 : : PyDoc_STRVAR(__about__,
583 : : "Heap queues\n\
584 : : \n\
585 : : [explanation by Fran\xc3\xa7ois Pinard]\n\
586 : : \n\
587 : : Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
588 : : all k, counting elements from 0. For the sake of comparison,\n\
589 : : non-existing elements are considered to be infinite. The interesting\n\
590 : : property of a heap is that a[0] is always its smallest element.\n"
591 : : "\n\
592 : : The strange invariant above is meant to be an efficient memory\n\
593 : : representation for a tournament. The numbers below are `k', not a[k]:\n\
594 : : \n\
595 : : 0\n\
596 : : \n\
597 : : 1 2\n\
598 : : \n\
599 : : 3 4 5 6\n\
600 : : \n\
601 : : 7 8 9 10 11 12 13 14\n\
602 : : \n\
603 : : 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30\n\
604 : : \n\
605 : : \n\
606 : : In the tree above, each cell `k' is topping `2*k+1' and `2*k+2'. In\n\
607 : : a usual binary tournament we see in sports, each cell is the winner\n\
608 : : over the two cells it tops, and we can trace the winner down the tree\n\
609 : : to see all opponents s/he had. However, in many computer applications\n\
610 : : of such tournaments, we do not need to trace the history of a winner.\n\
611 : : To be more memory efficient, when a winner is promoted, we try to\n\
612 : : replace it by something else at a lower level, and the rule becomes\n\
613 : : that a cell and the two cells it tops contain three different items,\n\
614 : : but the top cell \"wins\" over the two topped cells.\n"
615 : : "\n\
616 : : If this heap invariant is protected at all time, index 0 is clearly\n\
617 : : the overall winner. The simplest algorithmic way to remove it and\n\
618 : : find the \"next\" winner is to move some loser (let's say cell 30 in the\n\
619 : : diagram above) into the 0 position, and then percolate this new 0 down\n\
620 : : the tree, exchanging values, until the invariant is re-established.\n\
621 : : This is clearly logarithmic on the total number of items in the tree.\n\
622 : : By iterating over all items, you get an O(n ln n) sort.\n"
623 : : "\n\
624 : : A nice feature of this sort is that you can efficiently insert new\n\
625 : : items while the sort is going on, provided that the inserted items are\n\
626 : : not \"better\" than the last 0'th element you extracted. This is\n\
627 : : especially useful in simulation contexts, where the tree holds all\n\
628 : : incoming events, and the \"win\" condition means the smallest scheduled\n\
629 : : time. When an event schedule other events for execution, they are\n\
630 : : scheduled into the future, so they can easily go into the heap. So, a\n\
631 : : heap is a good structure for implementing schedulers (this is what I\n\
632 : : used for my MIDI sequencer :-).\n"
633 : : "\n\
634 : : Various structures for implementing schedulers have been extensively\n\
635 : : studied, and heaps are good for this, as they are reasonably speedy,\n\
636 : : the speed is almost constant, and the worst case is not much different\n\
637 : : than the average case. However, there are other representations which\n\
638 : : are more efficient overall, yet the worst cases might be terrible.\n"
639 : : "\n\
640 : : Heaps are also very useful in big disk sorts. You most probably all\n\
641 : : know that a big sort implies producing \"runs\" (which are pre-sorted\n\
642 : : sequences, which size is usually related to the amount of CPU memory),\n\
643 : : followed by a merging passes for these runs, which merging is often\n\
644 : : very cleverly organised[1]. It is very important that the initial\n\
645 : : sort produces the longest runs possible. Tournaments are a good way\n\
646 : : to that. If, using all the memory available to hold a tournament, you\n\
647 : : replace and percolate items that happen to fit the current run, you'll\n\
648 : : produce runs which are twice the size of the memory for random input,\n\
649 : : and much better for input fuzzily ordered.\n"
650 : : "\n\
651 : : Moreover, if you output the 0'th item on disk and get an input which\n\
652 : : may not fit in the current tournament (because the value \"wins\" over\n\
653 : : the last output value), it cannot fit in the heap, so the size of the\n\
654 : : heap decreases. The freed memory could be cleverly reused immediately\n\
655 : : for progressively building a second heap, which grows at exactly the\n\
656 : : same rate the first heap is melting. When the first heap completely\n\
657 : : vanishes, you switch heaps and start a new run. Clever and quite\n\
658 : : effective!\n\
659 : : \n\
660 : : In a word, heaps are useful memory structures to know. I use them in\n\
661 : : a few applications, and I think it is good to keep a `heap' module\n\
662 : : around. :-)\n"
663 : : "\n\
664 : : --------------------\n\
665 : : [1] The disk balancing algorithms which are current, nowadays, are\n\
666 : : more annoying than clever, and this is a consequence of the seeking\n\
667 : : capabilities of the disks. On devices which cannot seek, like big\n\
668 : : tape drives, the story was quite different, and one had to be very\n\
669 : : clever to ensure (far in advance) that each tape movement will be the\n\
670 : : most effective possible (that is, will best participate at\n\
671 : : \"progressing\" the merge). Some tapes were even able to read\n\
672 : : backwards, and this was also used to avoid the rewinding time.\n\
673 : : Believe me, real good tape sorts were quite spectacular to watch!\n\
674 : : From all times, sorting has always been a Great Art! :-)\n");
675 : :
676 : :
677 : : static int
678 : 1214 : heapq_exec(PyObject *m)
679 : : {
680 : 1214 : PyObject *about = PyUnicode_FromString(__about__);
681 [ - + ]: 1214 : if (PyModule_AddObject(m, "__about__", about) < 0) {
682 : 0 : Py_DECREF(about);
683 : 0 : return -1;
684 : : }
685 : 1214 : return 0;
686 : : }
687 : :
688 : : static struct PyModuleDef_Slot heapq_slots[] = {
689 : : {Py_mod_exec, heapq_exec},
690 : : {0, NULL}
691 : : };
692 : :
693 : : static struct PyModuleDef _heapqmodule = {
694 : : PyModuleDef_HEAD_INIT,
695 : : "_heapq",
696 : : module_doc,
697 : : 0,
698 : : heapq_methods,
699 : : heapq_slots,
700 : : NULL,
701 : : NULL,
702 : : NULL
703 : : };
704 : :
705 : : PyMODINIT_FUNC
706 : 1214 : PyInit__heapq(void)
707 : : {
708 : 1214 : return PyModuleDef_Init(&_heapqmodule);
709 : : }
|
