1 /* Drop in replacement for heapq.py 

     2 

     3 C implementation derived directly from heapq.py in Py2.3

     4 which was written by Kevin O'Connor, augmented by Tim Peters,

     5 annotated by François Pinard, and converted to C by Raymond Hettinger.

     6 

     7 */

     8 

     9 #include "Python.h"

    10 

    11 /* Older implementations of heapq used Py_LE for comparisons.  Now, it uses

    12    Py_LT so it will match min(), sorted(), and bisect().  Unfortunately, some

    13    client code (Twisted for example) relied on Py_LE, so this little function

    14    restores compatability by trying both.

    15 */

    16 static int

    17 cmp_lt(PyObject *x, PyObject *y)

    18 {

    19 	int cmp;

    20 	static PyObject *lt = NULL;

    21 

    22 	if (lt == NULL) {

    23 		lt = PyString_FromString("__lt__");

    24 		if (lt == NULL)

    25 			return -1;

    26 	}

    27 	if (PyObject_HasAttr(x, lt))

    28 		return PyObject_RichCompareBool(x, y, Py_LT);

    29 	cmp = PyObject_RichCompareBool(y, x, Py_LE);

    30 	if (cmp != -1)

    31 		cmp = 1 - cmp;

    32 	return cmp;

    33 }

    34 

    35 static int

    36 _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)

    37 {

    38 	PyObject *newitem, *parent;

    39 	int cmp;

    40 	Py_ssize_t parentpos;

    41 

    42 	assert(PyList_Check(heap));

    43 	if (pos >= PyList_GET_SIZE(heap)) {

    44 		PyErr_SetString(PyExc_IndexError, "index out of range");

    45 		return -1;

    46 	}

    47 

    48 	newitem = PyList_GET_ITEM(heap, pos);

    49 	Py_INCREF(newitem);

    50 	/* Follow the path to the root, moving parents down until finding

    51 	   a place newitem fits. */

    52 	while (pos > startpos){

    53 		parentpos = (pos - 1) >> 1;

    54 		parent = PyList_GET_ITEM(heap, parentpos);

    55 		cmp = cmp_lt(newitem, parent);

    56 		if (cmp == -1) {

    57 			Py_DECREF(newitem);

    58 			return -1;

    59 		}

    60 		if (cmp == 0)

    61 			break;

    62 		Py_INCREF(parent);

    63 		Py_DECREF(PyList_GET_ITEM(heap, pos));

    64 		PyList_SET_ITEM(heap, pos, parent);

    65 		pos = parentpos;

    66 	}

    67 	Py_DECREF(PyList_GET_ITEM(heap, pos));

    68 	PyList_SET_ITEM(heap, pos, newitem);

    69 	return 0;

    70 }

    71 

    72 static int

    73 _siftup(PyListObject *heap, Py_ssize_t pos)

    74 {

    75 	Py_ssize_t startpos, endpos, childpos, rightpos;

    76 	int cmp;

    77 	PyObject *newitem, *tmp;

    78 

    79 	assert(PyList_Check(heap));

    80 	endpos = PyList_GET_SIZE(heap);

    81 	startpos = pos;

    82 	if (pos >= endpos) {

    83 		PyErr_SetString(PyExc_IndexError, "index out of range");

    84 		return -1;

    85 	}

    86 	newitem = PyList_GET_ITEM(heap, pos);

    87 	Py_INCREF(newitem);

    88 

    89 	/* Bubble up the smaller child until hitting a leaf. */

    90 	childpos = 2*pos + 1;    /* leftmost child position  */

    91 	while (childpos < endpos) {

    92 		/* Set childpos to index of smaller child.   */

    93 		rightpos = childpos + 1;

    94 		if (rightpos < endpos) {

    95 			cmp = cmp_lt(

    96 				PyList_GET_ITEM(heap, childpos),

    97 				PyList_GET_ITEM(heap, rightpos));

    98 			if (cmp == -1) {

    99 				Py_DECREF(newitem);

   100 				return -1;

   101 			}

   102 			if (cmp == 0)

   103 				childpos = rightpos;

   104 		}

   105 		/* Move the smaller child up. */

   106 		tmp = PyList_GET_ITEM(heap, childpos);

   107 		Py_INCREF(tmp);

   108 		Py_DECREF(PyList_GET_ITEM(heap, pos));

   109 		PyList_SET_ITEM(heap, pos, tmp);

   110 		pos = childpos;

   111 		childpos = 2*pos + 1;

   112 	}

   113 

   114 	/* The leaf at pos is empty now.  Put newitem there, and and bubble

   115 	   it up to its final resting place (by sifting its parents down). */

   116 	Py_DECREF(PyList_GET_ITEM(heap, pos));

   117 	PyList_SET_ITEM(heap, pos, newitem);

   118 	return _siftdown(heap, startpos, pos);

   119 }

   120 

   121 static PyObject *

   122 heappush(PyObject *self, PyObject *args)

   123 {

   124 	PyObject *heap, *item;

   125 

   126 	if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item))

   127 		return NULL;

   128 

   129 	if (!PyList_Check(heap)) {

   130 		PyErr_SetString(PyExc_TypeError, "heap argument must be a list");

   131 		return NULL;

   132 	}

   133 

   134 	if (PyList_Append(heap, item) == -1)

   135 		return NULL;

   136 

   137 	if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1)

   138 		return NULL;

   139 	Py_INCREF(Py_None);

   140 	return Py_None;

   141 }

   142 

   143 PyDoc_STRVAR(heappush_doc,

   144 "Push item onto heap, maintaining the heap invariant.");

   145 

   146 static PyObject *

   147 heappop(PyObject *self, PyObject *heap)

   148 {

   149 	PyObject *lastelt, *returnitem;

   150 	Py_ssize_t n;

   151 

   152 	if (!PyList_Check(heap)) {

   153 		PyErr_SetString(PyExc_TypeError, "heap argument must be a list");

   154 		return NULL;

   155 	}

   156 

   157 	/* # raises appropriate IndexError if heap is empty */

   158 	n = PyList_GET_SIZE(heap);

   159 	if (n == 0) {

   160 		PyErr_SetString(PyExc_IndexError, "index out of range");

   161 		return NULL;

   162 	}

   163 

   164 	lastelt = PyList_GET_ITEM(heap, n-1) ;

   165 	Py_INCREF(lastelt);

   166 	PyList_SetSlice(heap, n-1, n, NULL);

   167 	n--;

   168 

   169 	if (!n) 

   170 		return lastelt;

   171 	returnitem = PyList_GET_ITEM(heap, 0);

   172 	PyList_SET_ITEM(heap, 0, lastelt);

   173 	if (_siftup((PyListObject *)heap, 0) == -1) {

   174 		Py_DECREF(returnitem);

   175 		return NULL;

   176 	}

   177 	return returnitem;

   178 }

   179 

   180 PyDoc_STRVAR(heappop_doc,

   181 "Pop the smallest item off the heap, maintaining the heap invariant.");

   182 

   183 static PyObject *

   184 heapreplace(PyObject *self, PyObject *args)

   185 {

   186 	PyObject *heap, *item, *returnitem;

   187 

   188 	if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item))

   189 		return NULL;

   190 

   191 	if (!PyList_Check(heap)) {

   192 		PyErr_SetString(PyExc_TypeError, "heap argument must be a list");

   193 		return NULL;

   194 	}

   195 

   196 	if (PyList_GET_SIZE(heap) < 1) {

   197 		PyErr_SetString(PyExc_IndexError, "index out of range");

   198 		return NULL;

   199 	}

   200 

   201 	returnitem = PyList_GET_ITEM(heap, 0);

   202 	Py_INCREF(item);

   203 	PyList_SET_ITEM(heap, 0, item);

   204 	if (_siftup((PyListObject *)heap, 0) == -1) {

   205 		Py_DECREF(returnitem);

   206 		return NULL;

   207 	}

   208 	return returnitem;

   209 }

   210 

   211 PyDoc_STRVAR(heapreplace_doc,

   212 "Pop and return the current smallest value, and add the new item.\n\

   213 \n\

   214 This is more efficient than heappop() followed by heappush(), and can be\n\

   215 more appropriate when using a fixed-size heap.  Note that the value\n\

   216 returned may be larger than item!  That constrains reasonable uses of\n\

   217 this routine unless written as part of a conditional replacement:\n\n\

   218         if item > heap[0]:\n\

   219             item = heapreplace(heap, item)\n");

   220 

   221 static PyObject *

   222 heappushpop(PyObject *self, PyObject *args)

   223 {

   224 	PyObject *heap, *item, *returnitem;

   225 	int cmp;

   226 

   227 	if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item))

   228 		return NULL;

   229 

   230 	if (!PyList_Check(heap)) {

   231 		PyErr_SetString(PyExc_TypeError, "heap argument must be a list");

   232 		return NULL;

   233 	}

   234 

   235 	if (PyList_GET_SIZE(heap) < 1) {

   236 		Py_INCREF(item);

   237 		return item;

   238 	}

   239 

   240 	cmp = cmp_lt(PyList_GET_ITEM(heap, 0), item);

   241 	if (cmp == -1)

   242 		return NULL;

   243 	if (cmp == 0) {

   244 		Py_INCREF(item);

   245 		return item;

   246 	}

   247 

   248 	returnitem = PyList_GET_ITEM(heap, 0);

   249 	Py_INCREF(item);

   250 	PyList_SET_ITEM(heap, 0, item);

   251 	if (_siftup((PyListObject *)heap, 0) == -1) {

   252 		Py_DECREF(returnitem);

   253 		return NULL;

   254 	}

   255 	return returnitem;

   256 }

   257 

   258 PyDoc_STRVAR(heappushpop_doc,

   259 "Push item on the heap, then pop and return the smallest item\n\

   260 from the heap. The combined action runs more efficiently than\n\

   261 heappush() followed by a separate call to heappop().");

   262 

   263 static PyObject *

   264 heapify(PyObject *self, PyObject *heap)

   265 {

   266 	Py_ssize_t i, n;

   267 

   268 	if (!PyList_Check(heap)) {

   269 		PyErr_SetString(PyExc_TypeError, "heap argument must be a list");

   270 		return NULL;

   271 	}

   272 

   273 	n = PyList_GET_SIZE(heap);

   274 	/* Transform bottom-up.  The largest index there's any point to

   275 	   looking at is the largest with a child index in-range, so must

   276 	   have 2*i + 1 < n, or i < (n-1)/2.  If n is even = 2*j, this is

   277 	   (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1.  If

   278 	   n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,

   279 	   and that's again n//2-1.

   280 	*/

   281 	for (i=n/2-1 ; i>=0 ; i--)

   282 		if(_siftup((PyListObject *)heap, i) == -1)

   283 			return NULL;

   284 	Py_INCREF(Py_None);

   285 	return Py_None;

   286 }

   287 

   288 PyDoc_STRVAR(heapify_doc,

   289 "Transform list into a heap, in-place, in O(len(heap)) time.");

   290 

   291 static PyObject *

   292 nlargest(PyObject *self, PyObject *args)

   293 {

   294 	PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem;

   295 	Py_ssize_t i, n;

   296 	int cmp;

   297 

   298 	if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable))

   299 		return NULL;

   300 

   301 	it = PyObject_GetIter(iterable);

   302 	if (it == NULL)

   303 		return NULL;

   304 

   305 	heap = PyList_New(0);

   306 	if (heap == NULL)

   307 		goto fail;

   308 

   309 	for (i=0 ; i<n ; i++ ){

   310 		elem = PyIter_Next(it);

   311 		if (elem == NULL) {

   312 			if (PyErr_Occurred())

   313 				goto fail;

   314 			else

   315 				goto sortit;

   316 		}

   317 		if (PyList_Append(heap, elem) == -1) {

   318 			Py_DECREF(elem);

   319 			goto fail;

   320 		}

   321 		Py_DECREF(elem);

   322 	}

   323 	if (PyList_GET_SIZE(heap) == 0)

   324 		goto sortit;

   325 

   326 	for (i=n/2-1 ; i>=0 ; i--)

   327 		if(_siftup((PyListObject *)heap, i) == -1)

   328 			goto fail;

   329 

   330 	sol = PyList_GET_ITEM(heap, 0);

   331 	while (1) {

   332 		elem = PyIter_Next(it);

   333 		if (elem == NULL) {

   334 			if (PyErr_Occurred())

   335 				goto fail;

   336 			else

   337 				goto sortit;

   338 		}

   339 		cmp = cmp_lt(sol, elem);

   340 		if (cmp == -1) {

   341 			Py_DECREF(elem);

   342 			goto fail;

   343 		}

   344 		if (cmp == 0) {

   345 			Py_DECREF(elem);

   346 			continue;

   347 		}

   348 		oldelem = PyList_GET_ITEM(heap, 0);

   349 		PyList_SET_ITEM(heap, 0, elem);

   350 		Py_DECREF(oldelem);

   351 		if (_siftup((PyListObject *)heap, 0) == -1)

   352 			goto fail;

   353 		sol = PyList_GET_ITEM(heap, 0);

   354 	}

   355 sortit:

   356 	if (PyList_Sort(heap) == -1)

   357 		goto fail;

   358 	if (PyList_Reverse(heap) == -1)

   359 		goto fail;

   360 	Py_DECREF(it);

   361 	return heap;

   362 

   363 fail:

   364 	Py_DECREF(it);

   365 	Py_XDECREF(heap);

   366 	return NULL;

   367 }

   368 

   369 PyDoc_STRVAR(nlargest_doc,

   370 "Find the n largest elements in a dataset.\n\

   371 \n\

   372 Equivalent to:  sorted(iterable, reverse=True)[:n]\n");

   373 

   374 static int

   375 _siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)

   376 {

   377 	PyObject *newitem, *parent;

   378 	int cmp;

   379 	Py_ssize_t parentpos;

   380 

   381 	assert(PyList_Check(heap));

   382 	if (pos >= PyList_GET_SIZE(heap)) {

   383 		PyErr_SetString(PyExc_IndexError, "index out of range");

   384 		return -1;

   385 	}

   386 

   387 	newitem = PyList_GET_ITEM(heap, pos);

   388 	Py_INCREF(newitem);

   389 	/* Follow the path to the root, moving parents down until finding

   390 	   a place newitem fits. */

   391 	while (pos > startpos){

   392 		parentpos = (pos - 1) >> 1;

   393 		parent = PyList_GET_ITEM(heap, parentpos);

   394 		cmp = cmp_lt(parent, newitem);

   395 		if (cmp == -1) {

   396 			Py_DECREF(newitem);

   397 			return -1;

   398 		}

   399 		if (cmp == 0)

   400 			break;

   401 		Py_INCREF(parent);

   402 		Py_DECREF(PyList_GET_ITEM(heap, pos));

   403 		PyList_SET_ITEM(heap, pos, parent);

   404 		pos = parentpos;

   405 	}

   406 	Py_DECREF(PyList_GET_ITEM(heap, pos));

   407 	PyList_SET_ITEM(heap, pos, newitem);

   408 	return 0;

   409 }

   410 

   411 static int

   412 _siftupmax(PyListObject *heap, Py_ssize_t pos)

   413 {

   414 	Py_ssize_t startpos, endpos, childpos, rightpos;

   415 	int cmp;

   416 	PyObject *newitem, *tmp;

   417 

   418 	assert(PyList_Check(heap));

   419 	endpos = PyList_GET_SIZE(heap);

   420 	startpos = pos;

   421 	if (pos >= endpos) {

   422 		PyErr_SetString(PyExc_IndexError, "index out of range");

   423 		return -1;

   424 	}

   425 	newitem = PyList_GET_ITEM(heap, pos);

   426 	Py_INCREF(newitem);

   427 

   428 	/* Bubble up the smaller child until hitting a leaf. */

   429 	childpos = 2*pos + 1;    /* leftmost child position  */

   430 	while (childpos < endpos) {

   431 		/* Set childpos to index of smaller child.   */

   432 		rightpos = childpos + 1;

   433 		if (rightpos < endpos) {

   434 			cmp = cmp_lt(

   435 				PyList_GET_ITEM(heap, rightpos),

   436 				PyList_GET_ITEM(heap, childpos));

   437 			if (cmp == -1) {

   438 				Py_DECREF(newitem);

   439 				return -1;

   440 			}

   441 			if (cmp == 0)

   442 				childpos = rightpos;

   443 		}

   444 		/* Move the smaller child up. */

   445 		tmp = PyList_GET_ITEM(heap, childpos);

   446 		Py_INCREF(tmp);

   447 		Py_DECREF(PyList_GET_ITEM(heap, pos));

   448 		PyList_SET_ITEM(heap, pos, tmp);

   449 		pos = childpos;

   450 		childpos = 2*pos + 1;

   451 	}

   452 

   453 	/* The leaf at pos is empty now.  Put newitem there, and and bubble

   454 	   it up to its final resting place (by sifting its parents down). */

   455 	Py_DECREF(PyList_GET_ITEM(heap, pos));

   456 	PyList_SET_ITEM(heap, pos, newitem);

   457 	return _siftdownmax(heap, startpos, pos);

   458 }

   459 

   460 static PyObject *

   461 nsmallest(PyObject *self, PyObject *args)

   462 {

   463 	PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem;

   464 	Py_ssize_t i, n;

   465 	int cmp;

   466 

   467 	if (!PyArg_ParseTuple(args, "nO:nsmallest", &n, &iterable))

   468 		return NULL;

   469 

   470 	it = PyObject_GetIter(iterable);

   471 	if (it == NULL)

   472 		return NULL;

   473 

   474 	heap = PyList_New(0);

   475 	if (heap == NULL)

   476 		goto fail;

   477 

   478 	for (i=0 ; i<n ; i++ ){

   479 		elem = PyIter_Next(it);

   480 		if (elem == NULL) {

   481 			if (PyErr_Occurred())

   482 				goto fail;

   483 			else

   484 				goto sortit;

   485 		}

   486 		if (PyList_Append(heap, elem) == -1) {

   487 			Py_DECREF(elem);

   488 			goto fail;

   489 		}

   490 		Py_DECREF(elem);

   491 	}

   492 	n = PyList_GET_SIZE(heap);

   493 	if (n == 0)

   494 		goto sortit;

   495 

   496 	for (i=n/2-1 ; i>=0 ; i--)

   497 		if(_siftupmax((PyListObject *)heap, i) == -1)

   498 			goto fail;

   499 

   500 	los = PyList_GET_ITEM(heap, 0);

   501 	while (1) {

   502 		elem = PyIter_Next(it);

   503 		if (elem == NULL) {

   504 			if (PyErr_Occurred())

   505 				goto fail;

   506 			else

   507 				goto sortit;

   508 		}

   509 		cmp = cmp_lt(elem, los);

   510 		if (cmp == -1) {

   511 			Py_DECREF(elem);

   512 			goto fail;

   513 		}

   514 		if (cmp == 0) {

   515 			Py_DECREF(elem);

   516 			continue;

   517 		}

   518 

   519 		oldelem = PyList_GET_ITEM(heap, 0);

   520 		PyList_SET_ITEM(heap, 0, elem);

   521 		Py_DECREF(oldelem);

   522 		if (_siftupmax((PyListObject *)heap, 0) == -1)

   523 			goto fail;

   524 		los = PyList_GET_ITEM(heap, 0);

   525 	}

   526 

   527 sortit:

   528 	if (PyList_Sort(heap) == -1)

   529 		goto fail;

   530 	Py_DECREF(it);

   531 	return heap;

   532 

   533 fail:

   534 	Py_DECREF(it);

   535 	Py_XDECREF(heap);

   536 	return NULL;

   537 }

   538 

   539 PyDoc_STRVAR(nsmallest_doc,

   540 "Find the n smallest elements in a dataset.\n\

   541 \n\

   542 Equivalent to:  sorted(iterable)[:n]\n");

   543 

   544 static PyMethodDef heapq_methods[] = {

   545 	{"heappush",	(PyCFunction)heappush,		

   546 		METH_VARARGS,	heappush_doc},

   547 	{"heappushpop",	(PyCFunction)heappushpop,		

   548 		METH_VARARGS,	heappushpop_doc},

   549 	{"heappop",	(PyCFunction)heappop,

   550 		METH_O,		heappop_doc},

   551 	{"heapreplace",	(PyCFunction)heapreplace,

   552 		METH_VARARGS,	heapreplace_doc},

   553 	{"heapify",	(PyCFunction)heapify,

   554 		METH_O,		heapify_doc},

   555 	{"nlargest",	(PyCFunction)nlargest,

   556 		METH_VARARGS,	nlargest_doc},

   557 	{"nsmallest",	(PyCFunction)nsmallest,

   558 		METH_VARARGS,	nsmallest_doc},

   559 	{NULL,		NULL}		/* sentinel */

   560 };

   561 

   562 PyDoc_STRVAR(module_doc,

   563 "Heap queue algorithm (a.k.a. priority queue).\n\

   564 \n\

   565 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\

   566 all k, counting elements from 0.  For the sake of comparison,\n\

   567 non-existing elements are considered to be infinite.  The interesting\n\

   568 property of a heap is that a[0] is always its smallest element.\n\

   569 \n\

   570 Usage:\n\

   571 \n\

   572 heap = []            # creates an empty heap\n\

   573 heappush(heap, item) # pushes a new item on the heap\n\

   574 item = heappop(heap) # pops the smallest item from the heap\n\

   575 item = heap[0]       # smallest item on the heap without popping it\n\

   576 heapify(x)           # transforms list into a heap, in-place, in linear time\n\

   577 item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\

   578                                # new item; the heap size is unchanged\n\

   579 \n\

   580 Our API differs from textbook heap algorithms as follows:\n\

   581 \n\

   582 - We use 0-based indexing.  This makes the relationship between the\n\

   583   index for a node and the indexes for its children slightly less\n\

   584   obvious, but is more suitable since Python uses 0-based indexing.\n\

   585 \n\

   586 - Our heappop() method returns the smallest item, not the largest.\n\

   587 \n\

   588 These two make it possible to view the heap as a regular Python list\n\

   589 without surprises: heap[0] is the smallest item, and heap.sort()\n\

   590 maintains the heap invariant!\n");

   591 

   592 

   593 PyDoc_STRVAR(__about__,

   594 "Heap queues\n\

   595 \n\

   596 [explanation by François Pinard]\n\

   597 \n\

   598 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\

   599 all k, counting elements from 0.  For the sake of comparison,\n\

   600 non-existing elements are considered to be infinite.  The interesting\n\

   601 property of a heap is that a[0] is always its smallest element.\n"

   602 "\n\

   603 The strange invariant above is meant to be an efficient memory\n\

   604 representation for a tournament.  The numbers below are `k', not a[k]:\n\

   605 \n\

   606                                    0\n\

   607 \n\

   608                   1                                 2\n\

   609 \n\

   610           3               4                5               6\n\

   611 \n\

   612       7       8       9       10      11      12      13      14\n\

   613 \n\

   614     15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30\n\

   615 \n\

   616 \n\

   617 In the tree above, each cell `k' is topping `2*k+1' and `2*k+2'.  In\n\

   618 an usual binary tournament we see in sports, each cell is the winner\n\

   619 over the two cells it tops, and we can trace the winner down the tree\n\

   620 to see all opponents s/he had.  However, in many computer applications\n\

   621 of such tournaments, we do not need to trace the history of a winner.\n\

   622 To be more memory efficient, when a winner is promoted, we try to\n\

   623 replace it by something else at a lower level, and the rule becomes\n\

   624 that a cell and the two cells it tops contain three different items,\n\

   625 but the top cell \"wins\" over the two topped cells.\n"

   626 "\n\

   627 If this heap invariant is protected at all time, index 0 is clearly\n\

   628 the overall winner.  The simplest algorithmic way to remove it and\n\

   629 find the \"next\" winner is to move some loser (let's say cell 30 in the\n\

   630 diagram above) into the 0 position, and then percolate this new 0 down\n\

   631 the tree, exchanging values, until the invariant is re-established.\n\

   632 This is clearly logarithmic on the total number of items in the tree.\n\

   633 By iterating over all items, you get an O(n ln n) sort.\n"

   634 "\n\

   635 A nice feature of this sort is that you can efficiently insert new\n\

   636 items while the sort is going on, provided that the inserted items are\n\

   637 not \"better\" than the last 0'th element you extracted.  This is\n\

   638 especially useful in simulation contexts, where the tree holds all\n\

   639 incoming events, and the \"win\" condition means the smallest scheduled\n\

   640 time.  When an event schedule other events for execution, they are\n\

   641 scheduled into the future, so they can easily go into the heap.  So, a\n\

   642 heap is a good structure for implementing schedulers (this is what I\n\

   643 used for my MIDI sequencer :-).\n"

   644 "\n\

   645 Various structures for implementing schedulers have been extensively\n\

   646 studied, and heaps are good for this, as they are reasonably speedy,\n\

   647 the speed is almost constant, and the worst case is not much different\n\

   648 than the average case.  However, there are other representations which\n\

   649 are more efficient overall, yet the worst cases might be terrible.\n"

   650 "\n\

   651 Heaps are also very useful in big disk sorts.  You most probably all\n\

   652 know that a big sort implies producing \"runs\" (which are pre-sorted\n\

   653 sequences, which size is usually related to the amount of CPU memory),\n\

   654 followed by a merging passes for these runs, which merging is often\n\

   655 very cleverly organised[1].  It is very important that the initial\n\

   656 sort produces the longest runs possible.  Tournaments are a good way\n\

   657 to that.  If, using all the memory available to hold a tournament, you\n\

   658 replace and percolate items that happen to fit the current run, you'll\n\

   659 produce runs which are twice the size of the memory for random input,\n\

   660 and much better for input fuzzily ordered.\n"

   661 "\n\

   662 Moreover, if you output the 0'th item on disk and get an input which\n\

   663 may not fit in the current tournament (because the value \"wins\" over\n\

   664 the last output value), it cannot fit in the heap, so the size of the\n\

   665 heap decreases.  The freed memory could be cleverly reused immediately\n\

   666 for progressively building a second heap, which grows at exactly the\n\

   667 same rate the first heap is melting.  When the first heap completely\n\

   668 vanishes, you switch heaps and start a new run.  Clever and quite\n\

   669 effective!\n\

   670 \n\

   671 In a word, heaps are useful memory structures to know.  I use them in\n\

   672 a few applications, and I think it is good to keep a `heap' module\n\

   673 around. :-)\n"

   674 "\n\

   675 --------------------\n\

   676 [1] The disk balancing algorithms which are current, nowadays, are\n\

   677 more annoying than clever, and this is a consequence of the seeking\n\

   678 capabilities of the disks.  On devices which cannot seek, like big\n\

   679 tape drives, the story was quite different, and one had to be very\n\

   680 clever to ensure (far in advance) that each tape movement will be the\n\

   681 most effective possible (that is, will best participate at\n\

   682 \"progressing\" the merge).  Some tapes were even able to read\n\

   683 backwards, and this was also used to avoid the rewinding time.\n\

   684 Believe me, real good tape sorts were quite spectacular to watch!\n\

   685 From all times, sorting has always been a Great Art! :-)\n");

   686 

   687 PyMODINIT_FUNC

   688 init_heapq(void)

   689 {

   690 	PyObject *m;

   691 

   692 	m = Py_InitModule3("_heapq", heapq_methods, module_doc);

   693 	if (m == NULL)

   694     		return;

   695 	PyModule_AddObject(m, "__about__", PyString_FromString(__about__));

   696 }

   697