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