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 /* 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 compatability 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 }
 697