Modules/_heapqmodule.c

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