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