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