AppPkg/Applications/Python/Python-2.7.10/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     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
  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 *
 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 *
 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 *
 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 *
 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 *
 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 *
 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
 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
 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 *
 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
 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