1 /* Drop in replacement for heapq.py
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.
12 _siftdown(PyListObject
*heap
, int startpos
, int pos
)
14 PyObject
*newitem
, *parent
;
17 assert(PyList_Check(heap
));
18 if (pos
>= PyList_GET_SIZE(heap
)) {
19 PyErr_SetString(PyExc_IndexError
, "index out of range");
23 newitem
= PyList_GET_ITEM(heap
, pos
);
25 /* Follow the path to the root, moving parents down until finding
26 a place newitem fits. */
27 while (pos
> startpos
){
28 parentpos
= (pos
- 1) >> 1;
29 parent
= PyList_GET_ITEM(heap
, parentpos
);
30 cmp
= PyObject_RichCompareBool(parent
, newitem
, Py_LE
);
38 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
39 PyList_SET_ITEM(heap
, pos
, parent
);
42 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
43 PyList_SET_ITEM(heap
, pos
, newitem
);
48 _siftup(PyListObject
*heap
, int pos
)
50 int startpos
, endpos
, childpos
, rightpos
;
52 PyObject
*newitem
, *tmp
;
54 assert(PyList_Check(heap
));
55 endpos
= PyList_GET_SIZE(heap
);
58 PyErr_SetString(PyExc_IndexError
, "index out of range");
61 newitem
= PyList_GET_ITEM(heap
, pos
);
64 /* Bubble up the smaller child until hitting a leaf. */
65 childpos
= 2*pos
+ 1; /* leftmost child position */
66 while (childpos
< endpos
) {
67 /* Set childpos to index of smaller child. */
68 rightpos
= childpos
+ 1;
69 if (rightpos
< endpos
) {
70 cmp
= PyObject_RichCompareBool(
71 PyList_GET_ITEM(heap
, rightpos
),
72 PyList_GET_ITEM(heap
, childpos
),
81 /* Move the smaller child up. */
82 tmp
= PyList_GET_ITEM(heap
, childpos
);
84 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
85 PyList_SET_ITEM(heap
, pos
, tmp
);
90 /* The leaf at pos is empty now. Put newitem there, and and bubble
91 it up to its final resting place (by sifting its parents down). */
92 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
93 PyList_SET_ITEM(heap
, pos
, newitem
);
94 return _siftdown(heap
, startpos
, pos
);
98 heappush(PyObject
*self
, PyObject
*args
)
100 PyObject
*heap
, *item
;
102 if (!PyArg_UnpackTuple(args
, "heappush", 2, 2, &heap
, &item
))
105 if (!PyList_Check(heap
)) {
106 PyErr_SetString(PyExc_TypeError
, "heap argument must be a list");
110 if (PyList_Append(heap
, item
) == -1)
113 if (_siftdown((PyListObject
*)heap
, 0, PyList_GET_SIZE(heap
)-1) == -1)
119 PyDoc_STRVAR(heappush_doc
,
120 "Push item onto heap, maintaining the heap invariant.");
123 heappop(PyObject
*self
, PyObject
*heap
)
125 PyObject
*lastelt
, *returnitem
;
128 if (!PyList_Check(heap
)) {
129 PyErr_SetString(PyExc_TypeError
, "heap argument must be a list");
133 /* # raises appropriate IndexError if heap is empty */
134 n
= PyList_GET_SIZE(heap
);
136 PyErr_SetString(PyExc_IndexError
, "index out of range");
140 lastelt
= PyList_GET_ITEM(heap
, n
-1) ;
142 PyList_SetSlice(heap
, n
-1, n
, NULL
);
147 returnitem
= PyList_GET_ITEM(heap
, 0);
148 PyList_SET_ITEM(heap
, 0, lastelt
);
149 if (_siftup((PyListObject
*)heap
, 0) == -1) {
150 Py_DECREF(returnitem
);
156 PyDoc_STRVAR(heappop_doc
,
157 "Pop the smallest item off the heap, maintaining the heap invariant.");
160 heapreplace(PyObject
*self
, PyObject
*args
)
162 PyObject
*heap
, *item
, *returnitem
;
164 if (!PyArg_UnpackTuple(args
, "heapreplace", 2, 2, &heap
, &item
))
167 if (!PyList_Check(heap
)) {
168 PyErr_SetString(PyExc_TypeError
, "heap argument must be a list");
172 if (PyList_GET_SIZE(heap
) < 1) {
173 PyErr_SetString(PyExc_IndexError
, "index out of range");
177 returnitem
= PyList_GET_ITEM(heap
, 0);
179 PyList_SET_ITEM(heap
, 0, item
);
180 if (_siftup((PyListObject
*)heap
, 0) == -1) {
181 Py_DECREF(returnitem
);
187 PyDoc_STRVAR(heapreplace_doc
,
188 "Pop and return the current smallest value, and add the new item.\n\
190 This is more efficient than heappop() followed by heappush(), and can be\n\
191 more appropriate when using a fixed-size heap. Note that the value\n\
192 returned may be larger than item! That constrains reasonable uses of\n\
193 this routine unless written as part of a conditional replacement:\n\n\
194 if item > heap[0]:\n\
195 item = heapreplace(heap, item)\n");
198 heapify(PyObject
*self
, PyObject
*heap
)
202 if (!PyList_Check(heap
)) {
203 PyErr_SetString(PyExc_TypeError
, "heap argument must be a list");
207 n
= PyList_GET_SIZE(heap
);
208 /* Transform bottom-up. The largest index there's any point to
209 looking at is the largest with a child index in-range, so must
210 have 2*i + 1 < n, or i < (n-1)/2. If n is even = 2*j, this is
211 (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If
212 n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,
213 and that's again n//2-1.
215 for (i
=n
/2-1 ; i
>=0 ; i
--)
216 if(_siftup((PyListObject
*)heap
, i
) == -1)
222 PyDoc_STRVAR(heapify_doc
,
223 "Transform list into a heap, in-place, in O(len(heap)) time.");
226 nlargest(PyObject
*self
, PyObject
*args
)
228 PyObject
*heap
=NULL
, *elem
, *iterable
, *sol
, *it
, *oldelem
;
231 if (!PyArg_ParseTuple(args
, "iO:nlargest", &n
, &iterable
))
234 it
= PyObject_GetIter(iterable
);
238 heap
= PyList_New(0);
242 for (i
=0 ; i
<n
; i
++ ){
243 elem
= PyIter_Next(it
);
245 if (PyErr_Occurred())
250 if (PyList_Append(heap
, elem
) == -1) {
256 if (PyList_GET_SIZE(heap
) == 0)
259 for (i
=n
/2-1 ; i
>=0 ; i
--)
260 if(_siftup((PyListObject
*)heap
, i
) == -1)
263 sol
= PyList_GET_ITEM(heap
, 0);
265 elem
= PyIter_Next(it
);
267 if (PyErr_Occurred())
272 if (PyObject_RichCompareBool(elem
, sol
, Py_LE
)) {
276 oldelem
= PyList_GET_ITEM(heap
, 0);
277 PyList_SET_ITEM(heap
, 0, elem
);
279 if (_siftup((PyListObject
*)heap
, 0) == -1)
281 sol
= PyList_GET_ITEM(heap
, 0);
284 if (PyList_Sort(heap
) == -1)
286 if (PyList_Reverse(heap
) == -1)
297 PyDoc_STRVAR(nlargest_doc
,
298 "Find the n largest elements in a dataset.\n\
300 Equivalent to: sorted(iterable, reverse=True)[:n]\n");
303 _siftdownmax(PyListObject
*heap
, int startpos
, int pos
)
305 PyObject
*newitem
, *parent
;
308 assert(PyList_Check(heap
));
309 if (pos
>= PyList_GET_SIZE(heap
)) {
310 PyErr_SetString(PyExc_IndexError
, "index out of range");
314 newitem
= PyList_GET_ITEM(heap
, pos
);
316 /* Follow the path to the root, moving parents down until finding
317 a place newitem fits. */
318 while (pos
> startpos
){
319 parentpos
= (pos
- 1) >> 1;
320 parent
= PyList_GET_ITEM(heap
, parentpos
);
321 cmp
= PyObject_RichCompareBool(newitem
, parent
, Py_LE
);
329 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
330 PyList_SET_ITEM(heap
, pos
, parent
);
333 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
334 PyList_SET_ITEM(heap
, pos
, newitem
);
339 _siftupmax(PyListObject
*heap
, int pos
)
341 int startpos
, endpos
, childpos
, rightpos
;
343 PyObject
*newitem
, *tmp
;
345 assert(PyList_Check(heap
));
346 endpos
= PyList_GET_SIZE(heap
);
349 PyErr_SetString(PyExc_IndexError
, "index out of range");
352 newitem
= PyList_GET_ITEM(heap
, pos
);
355 /* Bubble up the smaller child until hitting a leaf. */
356 childpos
= 2*pos
+ 1; /* leftmost child position */
357 while (childpos
< endpos
) {
358 /* Set childpos to index of smaller child. */
359 rightpos
= childpos
+ 1;
360 if (rightpos
< endpos
) {
361 cmp
= PyObject_RichCompareBool(
362 PyList_GET_ITEM(heap
, childpos
),
363 PyList_GET_ITEM(heap
, rightpos
),
372 /* Move the smaller child up. */
373 tmp
= PyList_GET_ITEM(heap
, childpos
);
375 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
376 PyList_SET_ITEM(heap
, pos
, tmp
);
378 childpos
= 2*pos
+ 1;
381 /* The leaf at pos is empty now. Put newitem there, and and bubble
382 it up to its final resting place (by sifting its parents down). */
383 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
384 PyList_SET_ITEM(heap
, pos
, newitem
);
385 return _siftdownmax(heap
, startpos
, pos
);
389 nsmallest(PyObject
*self
, PyObject
*args
)
391 PyObject
*heap
=NULL
, *elem
, *iterable
, *los
, *it
, *oldelem
;
394 if (!PyArg_ParseTuple(args
, "iO:nsmallest", &n
, &iterable
))
397 it
= PyObject_GetIter(iterable
);
401 heap
= PyList_New(0);
405 for (i
=0 ; i
<n
; i
++ ){
406 elem
= PyIter_Next(it
);
408 if (PyErr_Occurred())
413 if (PyList_Append(heap
, elem
) == -1) {
419 n
= PyList_GET_SIZE(heap
);
423 for (i
=n
/2-1 ; i
>=0 ; i
--)
424 if(_siftupmax((PyListObject
*)heap
, i
) == -1)
427 los
= PyList_GET_ITEM(heap
, 0);
429 elem
= PyIter_Next(it
);
431 if (PyErr_Occurred())
436 if (PyObject_RichCompareBool(los
, elem
, Py_LE
)) {
441 oldelem
= PyList_GET_ITEM(heap
, 0);
442 PyList_SET_ITEM(heap
, 0, elem
);
444 if (_siftupmax((PyListObject
*)heap
, 0) == -1)
446 los
= PyList_GET_ITEM(heap
, 0);
450 if (PyList_Sort(heap
) == -1)
461 PyDoc_STRVAR(nsmallest_doc
,
462 "Find the n smallest elements in a dataset.\n\
464 Equivalent to: sorted(iterable)[:n]\n");
466 static PyMethodDef heapq_methods
[] = {
467 {"heappush", (PyCFunction
)heappush
,
468 METH_VARARGS
, heappush_doc
},
469 {"heappop", (PyCFunction
)heappop
,
470 METH_O
, heappop_doc
},
471 {"heapreplace", (PyCFunction
)heapreplace
,
472 METH_VARARGS
, heapreplace_doc
},
473 {"heapify", (PyCFunction
)heapify
,
474 METH_O
, heapify_doc
},
475 {"nlargest", (PyCFunction
)nlargest
,
476 METH_VARARGS
, nlargest_doc
},
477 {"nsmallest", (PyCFunction
)nsmallest
,
478 METH_VARARGS
, nsmallest_doc
},
479 {NULL
, NULL
} /* sentinel */
482 PyDoc_STRVAR(module_doc
,
483 "Heap queue algorithm (a.k.a. priority queue).\n\
485 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
486 all k, counting elements from 0. For the sake of comparison,\n\
487 non-existing elements are considered to be infinite. The interesting\n\
488 property of a heap is that a[0] is always its smallest element.\n\
492 heap = [] # creates an empty heap\n\
493 heappush(heap, item) # pushes a new item on the heap\n\
494 item = heappop(heap) # pops the smallest item from the heap\n\
495 item = heap[0] # smallest item on the heap without popping it\n\
496 heapify(x) # transforms list into a heap, in-place, in linear time\n\
497 item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\
498 # new item; the heap size is unchanged\n\
500 Our API differs from textbook heap algorithms as follows:\n\
502 - We use 0-based indexing. This makes the relationship between the\n\
503 index for a node and the indexes for its children slightly less\n\
504 obvious, but is more suitable since Python uses 0-based indexing.\n\
506 - Our heappop() method returns the smallest item, not the largest.\n\
508 These two make it possible to view the heap as a regular Python list\n\
509 without surprises: heap[0] is the smallest item, and heap.sort()\n\
510 maintains the heap invariant!\n");
513 PyDoc_STRVAR(__about__
,
516 [explanation by François Pinard]\n\
518 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
519 all k, counting elements from 0. For the sake of comparison,\n\
520 non-existing elements are considered to be infinite. The interesting\n\
521 property of a heap is that a[0] is always its smallest element.\n"
523 The strange invariant above is meant to be an efficient memory\n\
524 representation for a tournament. The numbers below are `k', not a[k]:\n\
532 7 8 9 10 11 12 13 14\n\
534 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30\n\
537 In the tree above, each cell `k' is topping `2*k+1' and `2*k+2'. In\n\
538 an usual binary tournament we see in sports, each cell is the winner\n\
539 over the two cells it tops, and we can trace the winner down the tree\n\
540 to see all opponents s/he had. However, in many computer applications\n\
541 of such tournaments, we do not need to trace the history of a winner.\n\
542 To be more memory efficient, when a winner is promoted, we try to\n\
543 replace it by something else at a lower level, and the rule becomes\n\
544 that a cell and the two cells it tops contain three different items,\n\
545 but the top cell \"wins\" over the two topped cells.\n"
547 If this heap invariant is protected at all time, index 0 is clearly\n\
548 the overall winner. The simplest algorithmic way to remove it and\n\
549 find the \"next\" winner is to move some loser (let's say cell 30 in the\n\
550 diagram above) into the 0 position, and then percolate this new 0 down\n\
551 the tree, exchanging values, until the invariant is re-established.\n\
552 This is clearly logarithmic on the total number of items in the tree.\n\
553 By iterating over all items, you get an O(n ln n) sort.\n"
555 A nice feature of this sort is that you can efficiently insert new\n\
556 items while the sort is going on, provided that the inserted items are\n\
557 not \"better\" than the last 0'th element you extracted. This is\n\
558 especially useful in simulation contexts, where the tree holds all\n\
559 incoming events, and the \"win\" condition means the smallest scheduled\n\
560 time. When an event schedule other events for execution, they are\n\
561 scheduled into the future, so they can easily go into the heap. So, a\n\
562 heap is a good structure for implementing schedulers (this is what I\n\
563 used for my MIDI sequencer :-).\n"
565 Various structures for implementing schedulers have been extensively\n\
566 studied, and heaps are good for this, as they are reasonably speedy,\n\
567 the speed is almost constant, and the worst case is not much different\n\
568 than the average case. However, there are other representations which\n\
569 are more efficient overall, yet the worst cases might be terrible.\n"
571 Heaps are also very useful in big disk sorts. You most probably all\n\
572 know that a big sort implies producing \"runs\" (which are pre-sorted\n\
573 sequences, which size is usually related to the amount of CPU memory),\n\
574 followed by a merging passes for these runs, which merging is often\n\
575 very cleverly organised[1]. It is very important that the initial\n\
576 sort produces the longest runs possible. Tournaments are a good way\n\
577 to that. If, using all the memory available to hold a tournament, you\n\
578 replace and percolate items that happen to fit the current run, you'll\n\
579 produce runs which are twice the size of the memory for random input,\n\
580 and much better for input fuzzily ordered.\n"
582 Moreover, if you output the 0'th item on disk and get an input which\n\
583 may not fit in the current tournament (because the value \"wins\" over\n\
584 the last output value), it cannot fit in the heap, so the size of the\n\
585 heap decreases. The freed memory could be cleverly reused immediately\n\
586 for progressively building a second heap, which grows at exactly the\n\
587 same rate the first heap is melting. When the first heap completely\n\
588 vanishes, you switch heaps and start a new run. Clever and quite\n\
591 In a word, heaps are useful memory structures to know. I use them in\n\
592 a few applications, and I think it is good to keep a `heap' module\n\
595 --------------------\n\
596 [1] The disk balancing algorithms which are current, nowadays, are\n\
597 more annoying than clever, and this is a consequence of the seeking\n\
598 capabilities of the disks. On devices which cannot seek, like big\n\
599 tape drives, the story was quite different, and one had to be very\n\
600 clever to ensure (far in advance) that each tape movement will be the\n\
601 most effective possible (that is, will best participate at\n\
602 \"progressing\" the merge). Some tapes were even able to read\n\
603 backwards, and this was also used to avoid the rewinding time.\n\
604 Believe me, real good tape sorts were quite spectacular to watch!\n\
605 From all times, sorting has always been a Great Art! :-)\n");
612 m
= Py_InitModule3("_heapq", heapq_methods
, module_doc
);
615 PyModule_AddObject(m
, "__about__", PyString_FromString(__about__
));