17eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* Drop in replacement for heapq.py 27eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 37eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielC implementation derived directly from heapq.py in Py2.3 47eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielwhich was written by Kevin O'Connor, augmented by Tim Peters, 57eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielannotated by François Pinard, and converted to C by Raymond Hettinger. 67eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 77eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel*/ 87eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 97eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#include "Python.h" 107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* Older implementations of heapq used Py_LE for comparisons. Now, it uses 127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_LT so it will match min(), sorted(), and bisect(). Unfortunately, some 137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel client code (Twisted for example) relied on Py_LE, so this little function 147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel restores compatibility by trying both. 157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel*/ 167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielcmp_lt(PyObject *x, PyObject *y) 187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp; 207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel static PyObject *lt = NULL; 217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (lt == NULL) { 237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel lt = PyString_FromString("__lt__"); 247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (lt == NULL) 257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyObject_HasAttr(x, lt)) 287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyObject_RichCompareBool(x, y, Py_LT); 297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = PyObject_RichCompareBool(y, x, Py_LE); 307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp != -1) 317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = 1 - cmp; 327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return cmp; 337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel_siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) 377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *newitem, *parent; 397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t parentpos, size; 407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp; 417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(PyList_Check(heap)); 437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel size = PyList_GET_SIZE(heap); 447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (pos >= size) { 457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, "index out of range"); 467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Follow the path to the root, moving parents down until finding 507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel a place newitem fits. */ 517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel newitem = PyList_GET_ITEM(heap, pos); 527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (pos > startpos) { 537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel parentpos = (pos - 1) >> 1; 547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel parent = PyList_GET_ITEM(heap, parentpos); 557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = cmp_lt(newitem, parent); 567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == -1) 577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (size != PyList_GET_SIZE(heap)) { 597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_RuntimeError, 607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "list changed size during iteration"); 617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == 0) 647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel break; 657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel parent = PyList_GET_ITEM(heap, parentpos); 667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel newitem = PyList_GET_ITEM(heap, pos); 677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, parentpos, newitem); 687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, pos, parent); 697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel pos = parentpos; 707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel_siftup(PyListObject *heap, Py_ssize_t pos) 767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t startpos, endpos, childpos, rightpos, limit; 787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *tmp1, *tmp2; 797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp; 807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(PyList_Check(heap)); 827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel endpos = PyList_GET_SIZE(heap); 837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel startpos = pos; 847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (pos >= endpos) { 857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, "index out of range"); 867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Bubble up the smaller child until hitting a leaf. */ 907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel limit = endpos / 2; /* smallest pos that has no child */ 917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (pos < limit) { 927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Set childpos to index of smaller child. */ 937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel childpos = 2*pos + 1; /* leftmost child position */ 947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel rightpos = childpos + 1; 957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (rightpos < endpos) { 967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = cmp_lt( 977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_GET_ITEM(heap, childpos), 987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_GET_ITEM(heap, rightpos)); 997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == -1) 1007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 1017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == 0) 1027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel childpos = rightpos; 1037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (endpos != PyList_GET_SIZE(heap)) { 1047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_RuntimeError, 1057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "list changed size during iteration"); 1067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 1077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Move the smaller child up. */ 1107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel tmp1 = PyList_GET_ITEM(heap, childpos); 1117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel tmp2 = PyList_GET_ITEM(heap, pos); 1127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, childpos, tmp2); 1137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, pos, tmp1); 1147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel pos = childpos; 1157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Bubble it up to its final resting place (by sifting its parents down). */ 1177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return _siftdown(heap, startpos, pos); 1187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 1197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 1217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheappush(PyObject *self, PyObject *args) 1227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 1237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *heap, *item; 1247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item)) 1267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyList_Check(heap)) { 1297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); 1307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyList_Append(heap, item) == -1) 1347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1) 1377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(Py_None); 1397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return Py_None; 1407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 1417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(heappush_doc, 1437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant."); 1447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 1467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheappop(PyObject *self, PyObject *heap) 1477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 1487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *lastelt, *returnitem; 1497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t n; 1507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyList_Check(heap)) { 1527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); 1537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* # raises appropriate IndexError if heap is empty */ 1577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n = PyList_GET_SIZE(heap); 1587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (n == 0) { 1597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, "index out of range"); 1607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel lastelt = PyList_GET_ITEM(heap, n-1) ; 1647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(lastelt); 1657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SetSlice(heap, n-1, n, NULL); 1667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n--; 1677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!n) 1697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return lastelt; 1707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel returnitem = PyList_GET_ITEM(heap, 0); 1717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, 0, lastelt); 1727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (_siftup((PyListObject *)heap, 0) == -1) { 1737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(returnitem); 1747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return returnitem; 1777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 1787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(heappop_doc, 1807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"Pop the smallest item off the heap, maintaining the heap invariant."); 1817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 1837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheapreplace(PyObject *self, PyObject *args) 1847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 1857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *heap, *item, *returnitem; 1867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item)) 1887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyList_Check(heap)) { 1917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); 1927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyList_GET_SIZE(heap) < 1) { 1967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, "index out of range"); 1977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel returnitem = PyList_GET_ITEM(heap, 0); 2017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(item); 2027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, 0, item); 2037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (_siftup((PyListObject *)heap, 0) == -1) { 2047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(returnitem); 2057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return returnitem; 2087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 2097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(heapreplace_doc, 2117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"heapreplace(heap, item) -> value. Pop and return the current smallest value, and add the new item.\n\ 2127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 2137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielThis is more efficient than heappop() followed by heappush(), and can be\n\ 2147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielmore appropriate when using a fixed-size heap. Note that the value\n\ 2157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielreturned may be larger than item! That constrains reasonable uses of\n\ 2167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielthis routine unless written as part of a conditional replacement:\n\n\ 2177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if item > heap[0]:\n\ 2187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = heapreplace(heap, item)\n"); 2197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 2217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheappushpop(PyObject *self, PyObject *args) 2227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 2237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *heap, *item, *returnitem; 2247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp; 2257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item)) 2277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyList_Check(heap)) { 2307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); 2317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyList_GET_SIZE(heap) < 1) { 2357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(item); 2367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return item; 2377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = cmp_lt(PyList_GET_ITEM(heap, 0), item); 2407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == -1) 2417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == 0) { 2437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(item); 2447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return item; 2457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel returnitem = PyList_GET_ITEM(heap, 0); 2487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(item); 2497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, 0, item); 2507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (_siftup((PyListObject *)heap, 0) == -1) { 2517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(returnitem); 2527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return returnitem; 2557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 2567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(heappushpop_doc, 2587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"heappushpop(heap, item) -> value. Push item on the heap, then pop and return the smallest item\n\ 2597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielfrom the heap. The combined action runs more efficiently than\n\ 2607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheappush() followed by a separate call to heappop()."); 2617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 2637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheapify(PyObject *self, PyObject *heap) 2647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 2657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t i, n; 2667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyList_Check(heap)) { 2687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); 2697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n = PyList_GET_SIZE(heap); 2737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Transform bottom-up. The largest index there's any point to 2747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel looking at is the largest with a child index in-range, so must 2757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel have 2*i + 1 < n, or i < (n-1)/2. If n is even = 2*j, this is 2767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If 2777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest, 2787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel and that's again n//2-1. 2797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel */ 2807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (i=n/2-1 ; i>=0 ; i--) 2817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if(_siftup((PyListObject *)heap, i) == -1) 2827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(Py_None); 2847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return Py_None; 2857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 2867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(heapify_doc, 2887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"Transform list into a heap, in-place, in O(len(heap)) time."); 2897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 2917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielnlargest(PyObject *self, PyObject *args) 2927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 2937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem; 2947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t i, n; 2957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp; 2967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable)) 2987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it = PyObject_GetIter(iterable); 3017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it == NULL) 3027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel heap = PyList_New(0); 3057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (heap == NULL) 3067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 3077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (i=0 ; i<n ; i++ ){ 3097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel elem = PyIter_Next(it); 3107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (elem == NULL) { 3117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyErr_Occurred()) 3127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 3137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 3147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto sortit; 3157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyList_Append(heap, elem) == -1) { 3177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(elem); 3187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 3197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(elem); 3217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyList_GET_SIZE(heap) == 0) 3237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto sortit; 3247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (i=n/2-1 ; i>=0 ; i--) 3267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if(_siftup((PyListObject *)heap, i) == -1) 3277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 3287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel sol = PyList_GET_ITEM(heap, 0); 3307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (1) { 3317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel elem = PyIter_Next(it); 3327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (elem == NULL) { 3337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyErr_Occurred()) 3347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 3357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 3367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto sortit; 3377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = cmp_lt(sol, elem); 3397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == -1) { 3407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(elem); 3417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 3427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == 0) { 3447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(elem); 3457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel continue; 3467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel oldelem = PyList_GET_ITEM(heap, 0); 3487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, 0, elem); 3497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(oldelem); 3507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (_siftup((PyListObject *)heap, 0) == -1) 3517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 3527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel sol = PyList_GET_ITEM(heap, 0); 3537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielsortit: 3557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyList_Sort(heap) == -1) 3567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 3577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyList_Reverse(heap) == -1) 3587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 3597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 3607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return heap; 3617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielfail: 3637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 3647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(heap); 3657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 3677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(nlargest_doc, 3697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"Find the n largest elements in a dataset.\n\ 3707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 3717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielEquivalent to: sorted(iterable, reverse=True)[:n]\n"); 3727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 3747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel_siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) 3757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 3767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *newitem, *parent; 3777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp; 3787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t parentpos; 3797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(PyList_Check(heap)); 3817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (pos >= PyList_GET_SIZE(heap)) { 3827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, "index out of range"); 3837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 3847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel newitem = PyList_GET_ITEM(heap, pos); 3877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(newitem); 3887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Follow the path to the root, moving parents down until finding 3897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel a place newitem fits. */ 3907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (pos > startpos){ 3917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel parentpos = (pos - 1) >> 1; 3927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel parent = PyList_GET_ITEM(heap, parentpos); 3937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = cmp_lt(parent, newitem); 3947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == -1) { 3957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(newitem); 3967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 3977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == 0) 3997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel break; 4007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(parent); 4017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(PyList_GET_ITEM(heap, pos)); 4027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, pos, parent); 4037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel pos = parentpos; 4047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(PyList_GET_ITEM(heap, pos)); 4067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, pos, newitem); 4077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 4087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 4097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 4117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel_siftupmax(PyListObject *heap, Py_ssize_t pos) 4127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 4137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t startpos, endpos, childpos, rightpos, limit; 4147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp; 4157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *newitem, *tmp; 4167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(PyList_Check(heap)); 4187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel endpos = PyList_GET_SIZE(heap); 4197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel startpos = pos; 4207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (pos >= endpos) { 4217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, "index out of range"); 4227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 4237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel newitem = PyList_GET_ITEM(heap, pos); 4257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(newitem); 4267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Bubble up the smaller child until hitting a leaf. */ 4287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel limit = endpos / 2; /* smallest pos that has no child */ 4297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (pos < limit) { 4307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Set childpos to index of smaller child. */ 4317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel childpos = 2*pos + 1; /* leftmost child position */ 4327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel rightpos = childpos + 1; 4337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (rightpos < endpos) { 4347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = cmp_lt( 4357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_GET_ITEM(heap, rightpos), 4367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_GET_ITEM(heap, childpos)); 4377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == -1) { 4387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(newitem); 4397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 4407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == 0) 4427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel childpos = rightpos; 4437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Move the smaller child up. */ 4457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel tmp = PyList_GET_ITEM(heap, childpos); 4467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(tmp); 4477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(PyList_GET_ITEM(heap, pos)); 4487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, pos, tmp); 4497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel pos = childpos; 4507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* The leaf at pos is empty now. Put newitem there, and bubble 4537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it up to its final resting place (by sifting its parents down). */ 4547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(PyList_GET_ITEM(heap, pos)); 4557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, pos, newitem); 4567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return _siftdownmax(heap, startpos, pos); 4577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 4587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 4607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielnsmallest(PyObject *self, PyObject *args) 4617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 4627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem; 4637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t i, n; 4647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp; 4657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyArg_ParseTuple(args, "nO:nsmallest", &n, &iterable)) 4677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 4687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it = PyObject_GetIter(iterable); 4707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it == NULL) 4717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 4727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel heap = PyList_New(0); 4747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (heap == NULL) 4757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 4767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (i=0 ; i<n ; i++ ){ 4787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel elem = PyIter_Next(it); 4797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (elem == NULL) { 4807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyErr_Occurred()) 4817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 4827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 4837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto sortit; 4847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyList_Append(heap, elem) == -1) { 4867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(elem); 4877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 4887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(elem); 4907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n = PyList_GET_SIZE(heap); 4927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (n == 0) 4937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto sortit; 4947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (i=n/2-1 ; i>=0 ; i--) 4967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if(_siftupmax((PyListObject *)heap, i) == -1) 4977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 4987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel los = PyList_GET_ITEM(heap, 0); 5007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (1) { 5017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel elem = PyIter_Next(it); 5027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (elem == NULL) { 5037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyErr_Occurred()) 5047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 5057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 5067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto sortit; 5077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = cmp_lt(elem, los); 5097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == -1) { 5107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(elem); 5117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 5127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == 0) { 5147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(elem); 5157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel continue; 5167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel oldelem = PyList_GET_ITEM(heap, 0); 5197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyList_SET_ITEM(heap, 0, elem); 5207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(oldelem); 5217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (_siftupmax((PyListObject *)heap, 0) == -1) 5227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 5237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel los = PyList_GET_ITEM(heap, 0); 5247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielsortit: 5277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyList_Sort(heap) == -1) 5287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto fail; 5297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 5307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return heap; 5317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielfail: 5337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 5347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(heap); 5357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 5367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 5377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(nsmallest_doc, 5397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"Find the n smallest elements in a dataset.\n\ 5407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielEquivalent to: sorted(iterable)[:n]\n"); 5427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyMethodDef heapq_methods[] = { 5447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"heappush", (PyCFunction)heappush, 5457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_VARARGS, heappush_doc}, 5467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"heappushpop", (PyCFunction)heappushpop, 5477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_VARARGS, heappushpop_doc}, 5487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"heappop", (PyCFunction)heappop, 5497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_O, heappop_doc}, 5507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"heapreplace", (PyCFunction)heapreplace, 5517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_VARARGS, heapreplace_doc}, 5527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"heapify", (PyCFunction)heapify, 5537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_O, heapify_doc}, 5547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"nlargest", (PyCFunction)nlargest, 5557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_VARARGS, nlargest_doc}, 5567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"nsmallest", (PyCFunction)nsmallest, 5577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_VARARGS, nsmallest_doc}, 5587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {NULL, NULL} /* sentinel */ 5597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 5607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(module_doc, 5627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"Heap queue algorithm (a.k.a. priority queue).\n\ 5637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielHeaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\ 5657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielall k, counting elements from 0. For the sake of comparison,\n\ 5667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielnon-existing elements are considered to be infinite. The interesting\n\ 5677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielproperty of a heap is that a[0] is always its smallest element.\n\ 5687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielUsage:\n\ 5707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheap = [] # creates an empty heap\n\ 5727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheappush(heap, item) # pushes a new item on the heap\n\ 5737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielitem = heappop(heap) # pops the smallest item from the heap\n\ 5747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielitem = heap[0] # smallest item on the heap without popping it\n\ 5757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheapify(x) # transforms list into a heap, in-place, in linear time\n\ 5767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielitem = heapreplace(heap, item) # pops and returns smallest item, and adds\n\ 5777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel # new item; the heap size is unchanged\n\ 5787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielOur API differs from textbook heap algorithms as follows:\n\ 5807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel- We use 0-based indexing. This makes the relationship between the\n\ 5827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel index for a node and the indexes for its children slightly less\n\ 5837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel obvious, but is more suitable since Python uses 0-based indexing.\n\ 5847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel- Our heappop() method returns the smallest item, not the largest.\n\ 5867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielThese two make it possible to view the heap as a regular Python list\n\ 5887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielwithout surprises: heap[0] is the smallest item, and heap.sort()\n\ 5897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielmaintains the heap invariant!\n"); 5907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(__about__, 5937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"Heap queues\n\ 5947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel[explanation by Fran�ois Pinard]\n\ 5967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 5977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielHeaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\ 5987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielall k, counting elements from 0. For the sake of comparison,\n\ 5997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielnon-existing elements are considered to be infinite. The interesting\n\ 6007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielproperty of a heap is that a[0] is always its smallest element.\n" 6017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"\n\ 6027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielThe strange invariant above is meant to be an efficient memory\n\ 6037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielrepresentation for a tournament. The numbers below are `k', not a[k]:\n\ 6047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 6057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0\n\ 6067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 6077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1 2\n\ 6087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 6097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3 4 5 6\n\ 6107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 6117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7 8 9 10 11 12 13 14\n\ 6127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 6137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30\n\ 6147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 6157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 6167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielIn the tree above, each cell `k' is topping `2*k+1' and `2*k+2'. In\n\ 6177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielan usual binary tournament we see in sports, each cell is the winner\n\ 6187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielover the two cells it tops, and we can trace the winner down the tree\n\ 6197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielto see all opponents s/he had. However, in many computer applications\n\ 6207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielof such tournaments, we do not need to trace the history of a winner.\n\ 6217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielTo be more memory efficient, when a winner is promoted, we try to\n\ 6227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielreplace it by something else at a lower level, and the rule becomes\n\ 6237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielthat a cell and the two cells it tops contain three different items,\n\ 6247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielbut the top cell \"wins\" over the two topped cells.\n" 6257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"\n\ 6267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielIf this heap invariant is protected at all time, index 0 is clearly\n\ 6277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielthe overall winner. The simplest algorithmic way to remove it and\n\ 6287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielfind the \"next\" winner is to move some loser (let's say cell 30 in the\n\ 6297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldiagram above) into the 0 position, and then percolate this new 0 down\n\ 6307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielthe tree, exchanging values, until the invariant is re-established.\n\ 6317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielThis is clearly logarithmic on the total number of items in the tree.\n\ 6327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielBy iterating over all items, you get an O(n ln n) sort.\n" 6337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"\n\ 6347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielA nice feature of this sort is that you can efficiently insert new\n\ 6357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielitems while the sort is going on, provided that the inserted items are\n\ 6367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielnot \"better\" than the last 0'th element you extracted. This is\n\ 6377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielespecially useful in simulation contexts, where the tree holds all\n\ 6387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielincoming events, and the \"win\" condition means the smallest scheduled\n\ 6397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieltime. When an event schedule other events for execution, they are\n\ 6407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielscheduled into the future, so they can easily go into the heap. So, a\n\ 6417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheap is a good structure for implementing schedulers (this is what I\n\ 6427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielused for my MIDI sequencer :-).\n" 6437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"\n\ 6447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielVarious structures for implementing schedulers have been extensively\n\ 6457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstudied, and heaps are good for this, as they are reasonably speedy,\n\ 6467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielthe speed is almost constant, and the worst case is not much different\n\ 6477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielthan the average case. However, there are other representations which\n\ 6487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielare more efficient overall, yet the worst cases might be terrible.\n" 6497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"\n\ 6507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielHeaps are also very useful in big disk sorts. You most probably all\n\ 6517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielknow that a big sort implies producing \"runs\" (which are pre-sorted\n\ 6527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielsequences, which size is usually related to the amount of CPU memory),\n\ 6537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielfollowed by a merging passes for these runs, which merging is often\n\ 6547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielvery cleverly organised[1]. It is very important that the initial\n\ 6557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielsort produces the longest runs possible. Tournaments are a good way\n\ 6567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielto that. If, using all the memory available to hold a tournament, you\n\ 6577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielreplace and percolate items that happen to fit the current run, you'll\n\ 6587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielproduce runs which are twice the size of the memory for random input,\n\ 6597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieland much better for input fuzzily ordered.\n" 6607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"\n\ 6617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielMoreover, if you output the 0'th item on disk and get an input which\n\ 6627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielmay not fit in the current tournament (because the value \"wins\" over\n\ 6637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielthe last output value), it cannot fit in the heap, so the size of the\n\ 6647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielheap decreases. The freed memory could be cleverly reused immediately\n\ 6657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielfor progressively building a second heap, which grows at exactly the\n\ 6667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielsame rate the first heap is melting. When the first heap completely\n\ 6677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielvanishes, you switch heaps and start a new run. Clever and quite\n\ 6687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieleffective!\n\ 6697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 6707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielIn a word, heaps are useful memory structures to know. I use them in\n\ 6717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniela few applications, and I think it is good to keep a `heap' module\n\ 6727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielaround. :-)\n" 6737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"\n\ 6747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel--------------------\n\ 6757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel[1] The disk balancing algorithms which are current, nowadays, are\n\ 6767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielmore annoying than clever, and this is a consequence of the seeking\n\ 6777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielcapabilities of the disks. On devices which cannot seek, like big\n\ 6787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieltape drives, the story was quite different, and one had to be very\n\ 6797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielclever to ensure (far in advance) that each tape movement will be the\n\ 6807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielmost effective possible (that is, will best participate at\n\ 6817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\"progressing\" the merge). Some tapes were even able to read\n\ 6827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielbackwards, and this was also used to avoid the rewinding time.\n\ 6837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielBelieve me, real good tape sorts were quite spectacular to watch!\n\ 6847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielFrom all times, sorting has always been a Great Art! :-)\n"); 6857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyMODINIT_FUNC 6877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielinit_heapq(void) 6887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 6897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *m; 6907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m = Py_InitModule3("_heapq", heapq_methods, module_doc); 6927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (m == NULL) 6937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return; 6947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyModule_AddObject(m, "__about__", PyString_FromString(__about__)); 6957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 6967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 697