AppPkg/Applications/Python/Python-2.7.2/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 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 }
 697