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 returnitem = PyList_GET_ITEM(heap, 0);
248 Py_INCREF(item);
249 PyList_SET_ITEM(heap, 0, item);
250 if (_siftup((PyListObject *)heap, 0) == -1) {
251 Py_DECREF(returnitem);
252 return NULL;
253 }
254 return returnitem;
255 }
256
257 PyDoc_STRVAR(heappushpop_doc,
258 "heappushpop(heap, item) -> value. Push item on the heap, then pop and return the smallest item\n\
259 from the heap. The combined action runs more efficiently than\n\
260 heappush() followed by a separate call to heappop().");
261
262 static PyObject *
heapify(PyObject * self,PyObject * heap)263 heapify(PyObject *self, PyObject *heap)
264 {
265 Py_ssize_t i, n;
266
267 if (!PyList_Check(heap)) {
268 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
269 return NULL;
270 }
271
272 n = PyList_GET_SIZE(heap);
273 /* Transform bottom-up. The largest index there's any point to
274 looking at is the largest with a child index in-range, so must
275 have 2*i + 1 < n, or i < (n-1)/2. If n is even = 2*j, this is
276 (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If
277 n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,
278 and that's again n//2-1.
279 */
280 for (i=n/2-1 ; i>=0 ; i--)
281 if(_siftup((PyListObject *)heap, i) == -1)
282 return NULL;
283 Py_INCREF(Py_None);
284 return Py_None;
285 }
286
287 PyDoc_STRVAR(heapify_doc,
288 "Transform list into a heap, in-place, in O(len(heap)) time.");
289
290 static PyObject *
nlargest(PyObject * self,PyObject * args)291 nlargest(PyObject *self, PyObject *args)
292 {
293 PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem;
294 Py_ssize_t i, n;
295 int cmp;
296
297 if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable))
298 return NULL;
299
300 it = PyObject_GetIter(iterable);
301 if (it == NULL)
302 return NULL;
303
304 heap = PyList_New(0);
305 if (heap == NULL)
306 goto fail;
307
308 for (i=0 ; i<n ; i++ ){
309 elem = PyIter_Next(it);
310 if (elem == NULL) {
311 if (PyErr_Occurred())
312 goto fail;
313 else
314 goto sortit;
315 }
316 if (PyList_Append(heap, elem) == -1) {
317 Py_DECREF(elem);
318 goto fail;
319 }
320 Py_DECREF(elem);
321 }
322 if (PyList_GET_SIZE(heap) == 0)
323 goto sortit;
324
325 for (i=n/2-1 ; i>=0 ; i--)
326 if(_siftup((PyListObject *)heap, i) == -1)
327 goto fail;
328
329 sol = PyList_GET_ITEM(heap, 0);
330 while (1) {
331 elem = PyIter_Next(it);
332 if (elem == NULL) {
333 if (PyErr_Occurred())
334 goto fail;
335 else
336 goto sortit;
337 }
338 cmp = cmp_lt(sol, elem);
339 if (cmp == -1) {
340 Py_DECREF(elem);
341 goto fail;
342 }
343 if (cmp == 0) {
344 Py_DECREF(elem);
345 continue;
346 }
347 oldelem = PyList_GET_ITEM(heap, 0);
348 PyList_SET_ITEM(heap, 0, elem);
349 Py_DECREF(oldelem);
350 if (_siftup((PyListObject *)heap, 0) == -1)
351 goto fail;
352 sol = PyList_GET_ITEM(heap, 0);
353 }
354 sortit:
355 if (PyList_Sort(heap) == -1)
356 goto fail;
357 if (PyList_Reverse(heap) == -1)
358 goto fail;
359 Py_DECREF(it);
360 return heap;
361
362 fail:
363 Py_DECREF(it);
364 Py_XDECREF(heap);
365 return NULL;
366 }
367
368 PyDoc_STRVAR(nlargest_doc,
369 "Find the n largest elements in a dataset.\n\
370 \n\
371 Equivalent to: sorted(iterable, reverse=True)[:n]\n");
372
373 static int
_siftdownmax(PyListObject * heap,Py_ssize_t startpos,Py_ssize_t pos)374 _siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
375 {
376 PyObject *newitem, *parent;
377 int cmp;
378 Py_ssize_t parentpos;
379
380 assert(PyList_Check(heap));
381 if (pos >= PyList_GET_SIZE(heap)) {
382 PyErr_SetString(PyExc_IndexError, "index out of range");
383 return -1;
384 }
385
386 newitem = PyList_GET_ITEM(heap, pos);
387 Py_INCREF(newitem);
388 /* Follow the path to the root, moving parents down until finding
389 a place newitem fits. */
390 while (pos > startpos){
391 parentpos = (pos - 1) >> 1;
392 parent = PyList_GET_ITEM(heap, parentpos);
393 cmp = cmp_lt(parent, newitem);
394 if (cmp == -1) {
395 Py_DECREF(newitem);
396 return -1;
397 }
398 if (cmp == 0)
399 break;
400 Py_INCREF(parent);
401 Py_DECREF(PyList_GET_ITEM(heap, pos));
402 PyList_SET_ITEM(heap, pos, parent);
403 pos = parentpos;
404 }
405 Py_DECREF(PyList_GET_ITEM(heap, pos));
406 PyList_SET_ITEM(heap, pos, newitem);
407 return 0;
408 }
409
410 static int
_siftupmax(PyListObject * heap,Py_ssize_t pos)411 _siftupmax(PyListObject *heap, Py_ssize_t pos)
412 {
413 Py_ssize_t startpos, endpos, childpos, rightpos, limit;
414 int cmp;
415 PyObject *newitem, *tmp;
416
417 assert(PyList_Check(heap));
418 endpos = PyList_GET_SIZE(heap);
419 startpos = pos;
420 if (pos >= endpos) {
421 PyErr_SetString(PyExc_IndexError, "index out of range");
422 return -1;
423 }
424 newitem = PyList_GET_ITEM(heap, pos);
425 Py_INCREF(newitem);
426
427 /* Bubble up the smaller child until hitting a leaf. */
428 limit = endpos / 2; /* smallest pos that has no child */
429 while (pos < limit) {
430 /* Set childpos to index of smaller child. */
431 childpos = 2*pos + 1; /* leftmost child position */
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 }
451
452 /* The leaf at pos is empty now. Put newitem there, and bubble
453 it up to its final resting place (by sifting its parents down). */
454 Py_DECREF(PyList_GET_ITEM(heap, pos));
455 PyList_SET_ITEM(heap, pos, newitem);
456 return _siftdownmax(heap, startpos, pos);
457 }
458
459 static PyObject *
nsmallest(PyObject * self,PyObject * args)460 nsmallest(PyObject *self, PyObject *args)
461 {
462 PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem;
463 Py_ssize_t i, n;
464 int cmp;
465
466 if (!PyArg_ParseTuple(args, "nO:nsmallest", &n, &iterable))
467 return NULL;
468
469 it = PyObject_GetIter(iterable);
470 if (it == NULL)
471 return NULL;
472
473 heap = PyList_New(0);
474 if (heap == NULL)
475 goto fail;
476
477 for (i=0 ; i<n ; i++ ){
478 elem = PyIter_Next(it);
479 if (elem == NULL) {
480 if (PyErr_Occurred())
481 goto fail;
482 else
483 goto sortit;
484 }
485 if (PyList_Append(heap, elem) == -1) {
486 Py_DECREF(elem);
487 goto fail;
488 }
489 Py_DECREF(elem);
490 }
491 n = PyList_GET_SIZE(heap);
492 if (n == 0)
493 goto sortit;
494
495 for (i=n/2-1 ; i>=0 ; i--)
496 if(_siftupmax((PyListObject *)heap, i) == -1)
497 goto fail;
498
499 los = PyList_GET_ITEM(heap, 0);
500 while (1) {
501 elem = PyIter_Next(it);
502 if (elem == NULL) {
503 if (PyErr_Occurred())
504 goto fail;
505 else
506 goto sortit;
507 }
508 cmp = cmp_lt(elem, los);
509 if (cmp == -1) {
510 Py_DECREF(elem);
511 goto fail;
512 }
513 if (cmp == 0) {
514 Py_DECREF(elem);
515 continue;
516 }
517
518 oldelem = PyList_GET_ITEM(heap, 0);
519 PyList_SET_ITEM(heap, 0, elem);
520 Py_DECREF(oldelem);
521 if (_siftupmax((PyListObject *)heap, 0) == -1)
522 goto fail;
523 los = PyList_GET_ITEM(heap, 0);
524 }
525
526 sortit:
527 if (PyList_Sort(heap) == -1)
528 goto fail;
529 Py_DECREF(it);
530 return heap;
531
532 fail:
533 Py_DECREF(it);
534 Py_XDECREF(heap);
535 return NULL;
536 }
537
538 PyDoc_STRVAR(nsmallest_doc,
539 "Find the n smallest elements in a dataset.\n\
540 \n\
541 Equivalent to: sorted(iterable)[:n]\n");
542
543 static PyMethodDef heapq_methods[] = {
544 {"heappush", (PyCFunction)heappush,
545 METH_VARARGS, heappush_doc},
546 {"heappushpop", (PyCFunction)heappushpop,
547 METH_VARARGS, heappushpop_doc},
548 {"heappop", (PyCFunction)heappop,
549 METH_O, heappop_doc},
550 {"heapreplace", (PyCFunction)heapreplace,
551 METH_VARARGS, heapreplace_doc},
552 {"heapify", (PyCFunction)heapify,
553 METH_O, heapify_doc},
554 {"nlargest", (PyCFunction)nlargest,
555 METH_VARARGS, nlargest_doc},
556 {"nsmallest", (PyCFunction)nsmallest,
557 METH_VARARGS, nsmallest_doc},
558 {NULL, NULL} /* sentinel */
559 };
560
561 PyDoc_STRVAR(module_doc,
562 "Heap queue algorithm (a.k.a. priority queue).\n\
563 \n\
564 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
565 all k, counting elements from 0. For the sake of comparison,\n\
566 non-existing elements are considered to be infinite. The interesting\n\
567 property of a heap is that a[0] is always its smallest element.\n\
568 \n\
569 Usage:\n\
570 \n\
571 heap = [] # creates an empty heap\n\
572 heappush(heap, item) # pushes a new item on the heap\n\
573 item = heappop(heap) # pops the smallest item from the heap\n\
574 item = heap[0] # smallest item on the heap without popping it\n\
575 heapify(x) # transforms list into a heap, in-place, in linear time\n\
576 item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\
577 # new item; the heap size is unchanged\n\
578 \n\
579 Our API differs from textbook heap algorithms as follows:\n\
580 \n\
581 - We use 0-based indexing. This makes the relationship between the\n\
582 index for a node and the indexes for its children slightly less\n\
583 obvious, but is more suitable since Python uses 0-based indexing.\n\
584 \n\
585 - Our heappop() method returns the smallest item, not the largest.\n\
586 \n\
587 These two make it possible to view the heap as a regular Python list\n\
588 without surprises: heap[0] is the smallest item, and heap.sort()\n\
589 maintains the heap invariant!\n");
590
591
592 PyDoc_STRVAR(__about__,
593 "Heap queues\n\
594 \n\
595 [explanation by Fran�ois Pinard]\n\
596 \n\
597 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
598 all k, counting elements from 0. For the sake of comparison,\n\
599 non-existing elements are considered to be infinite. The interesting\n\
600 property of a heap is that a[0] is always its smallest element.\n"
601 "\n\
602 The strange invariant above is meant to be an efficient memory\n\
603 representation for a tournament. The numbers below are `k', not a[k]:\n\
604 \n\
605 0\n\
606 \n\
607 1 2\n\
608 \n\
609 3 4 5 6\n\
610 \n\
611 7 8 9 10 11 12 13 14\n\
612 \n\
613 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30\n\
614 \n\
615 \n\
616 In the tree above, each cell `k' is topping `2*k+1' and `2*k+2'. In\n\
617 an usual binary tournament we see in sports, each cell is the winner\n\
618 over the two cells it tops, and we can trace the winner down the tree\n\
619 to see all opponents s/he had. However, in many computer applications\n\
620 of such tournaments, we do not need to trace the history of a winner.\n\
621 To be more memory efficient, when a winner is promoted, we try to\n\
622 replace it by something else at a lower level, and the rule becomes\n\
623 that a cell and the two cells it tops contain three different items,\n\
624 but the top cell \"wins\" over the two topped cells.\n"
625 "\n\
626 If this heap invariant is protected at all time, index 0 is clearly\n\
627 the overall winner. The simplest algorithmic way to remove it and\n\
628 find the \"next\" winner is to move some loser (let's say cell 30 in the\n\
629 diagram above) into the 0 position, and then percolate this new 0 down\n\
630 the tree, exchanging values, until the invariant is re-established.\n\
631 This is clearly logarithmic on the total number of items in the tree.\n\
632 By iterating over all items, you get an O(n ln n) sort.\n"
633 "\n\
634 A nice feature of this sort is that you can efficiently insert new\n\
635 items while the sort is going on, provided that the inserted items are\n\
636 not \"better\" than the last 0'th element you extracted. This is\n\
637 especially useful in simulation contexts, where the tree holds all\n\
638 incoming events, and the \"win\" condition means the smallest scheduled\n\
639 time. When an event schedule other events for execution, they are\n\
640 scheduled into the future, so they can easily go into the heap. So, a\n\
641 heap is a good structure for implementing schedulers (this is what I\n\
642 used for my MIDI sequencer :-).\n"
643 "\n\
644 Various structures for implementing schedulers have been extensively\n\
645 studied, and heaps are good for this, as they are reasonably speedy,\n\
646 the speed is almost constant, and the worst case is not much different\n\
647 than the average case. However, there are other representations which\n\
648 are more efficient overall, yet the worst cases might be terrible.\n"
649 "\n\
650 Heaps are also very useful in big disk sorts. You most probably all\n\
651 know that a big sort implies producing \"runs\" (which are pre-sorted\n\
652 sequences, which size is usually related to the amount of CPU memory),\n\
653 followed by a merging passes for these runs, which merging is often\n\
654 very cleverly organised[1]. It is very important that the initial\n\
655 sort produces the longest runs possible. Tournaments are a good way\n\
656 to that. If, using all the memory available to hold a tournament, you\n\
657 replace and percolate items that happen to fit the current run, you'll\n\
658 produce runs which are twice the size of the memory for random input,\n\
659 and much better for input fuzzily ordered.\n"
660 "\n\
661 Moreover, if you output the 0'th item on disk and get an input which\n\
662 may not fit in the current tournament (because the value \"wins\" over\n\
663 the last output value), it cannot fit in the heap, so the size of the\n\
664 heap decreases. The freed memory could be cleverly reused immediately\n\
665 for progressively building a second heap, which grows at exactly the\n\
666 same rate the first heap is melting. When the first heap completely\n\
667 vanishes, you switch heaps and start a new run. Clever and quite\n\
668 effective!\n\
669 \n\
670 In a word, heaps are useful memory structures to know. I use them in\n\
671 a few applications, and I think it is good to keep a `heap' module\n\
672 around. :-)\n"
673 "\n\
674 --------------------\n\
675 [1] The disk balancing algorithms which are current, nowadays, are\n\
676 more annoying than clever, and this is a consequence of the seeking\n\
677 capabilities of the disks. On devices which cannot seek, like big\n\
678 tape drives, the story was quite different, and one had to be very\n\
679 clever to ensure (far in advance) that each tape movement will be the\n\
680 most effective possible (that is, will best participate at\n\
681 \"progressing\" the merge). Some tapes were even able to read\n\
682 backwards, and this was also used to avoid the rewinding time.\n\
683 Believe me, real good tape sorts were quite spectacular to watch!\n\
684 From all times, sorting has always been a Great Art! :-)\n");
685
686 PyMODINIT_FUNC
init_heapq(void)687 init_heapq(void)
688 {
689 PyObject *m;
690
691 m = Py_InitModule3("_heapq", heapq_methods, module_doc);
692 if (m == NULL)
693 return;
694 PyModule_AddObject(m, "__about__", PyString_FromString(__about__));
695 }
696
697