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
, Py_ssize_t startpos
, Py_ssize_t pos
)
14 PyObject
*newitem
, *parent
;
18 assert(PyList_Check(heap
));
19 if (pos
>= PyList_GET_SIZE(heap
)) {
20 PyErr_SetString(PyExc_IndexError
, "index out of range");
24 newitem
= PyList_GET_ITEM(heap
, pos
);
26 /* Follow the path to the root, moving parents down until finding
27 a place newitem fits. */
28 while (pos
> startpos
){
29 parentpos
= (pos
- 1) >> 1;
30 parent
= PyList_GET_ITEM(heap
, parentpos
);
31 cmp
= PyObject_RichCompareBool(parent
, newitem
, Py_LE
);
39 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
40 PyList_SET_ITEM(heap
, pos
, parent
);
43 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
44 PyList_SET_ITEM(heap
, pos
, newitem
);
49 _siftup(PyListObject
*heap
, Py_ssize_t pos
)
51 Py_ssize_t startpos
, endpos
, childpos
, rightpos
;
53 PyObject
*newitem
, *tmp
;
55 assert(PyList_Check(heap
));
56 endpos
= PyList_GET_SIZE(heap
);
59 PyErr_SetString(PyExc_IndexError
, "index out of range");
62 newitem
= PyList_GET_ITEM(heap
, pos
);
65 /* Bubble up the smaller child until hitting a leaf. */
66 childpos
= 2*pos
+ 1; /* leftmost child position */
67 while (childpos
< endpos
) {
68 /* Set childpos to index of smaller child. */
69 rightpos
= childpos
+ 1;
70 if (rightpos
< endpos
) {
71 cmp
= PyObject_RichCompareBool(
72 PyList_GET_ITEM(heap
, rightpos
),
73 PyList_GET_ITEM(heap
, childpos
),
82 /* Move the smaller child up. */
83 tmp
= PyList_GET_ITEM(heap
, childpos
);
85 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
86 PyList_SET_ITEM(heap
, pos
, tmp
);
91 /* The leaf at pos is empty now. Put newitem there, and and bubble
92 it up to its final resting place (by sifting its parents down). */
93 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
94 PyList_SET_ITEM(heap
, pos
, newitem
);
95 return _siftdown(heap
, startpos
, pos
);
99 heappush(PyObject
*self
, PyObject
*args
)
101 PyObject
*heap
, *item
;
103 if (!PyArg_UnpackTuple(args
, "heappush", 2, 2, &heap
, &item
))
106 if (!PyList_Check(heap
)) {
107 PyErr_SetString(PyExc_TypeError
, "heap argument must be a list");
111 if (PyList_Append(heap
, item
) == -1)
114 if (_siftdown((PyListObject
*)heap
, 0, PyList_GET_SIZE(heap
)-1) == -1)
120 PyDoc_STRVAR(heappush_doc
,
121 "Push item onto heap, maintaining the heap invariant.");
124 heappop(PyObject
*self
, PyObject
*heap
)
126 PyObject
*lastelt
, *returnitem
;
129 if (!PyList_Check(heap
)) {
130 PyErr_SetString(PyExc_TypeError
, "heap argument must be a list");
134 /* # raises appropriate IndexError if heap is empty */
135 n
= PyList_GET_SIZE(heap
);
137 PyErr_SetString(PyExc_IndexError
, "index out of range");
141 lastelt
= PyList_GET_ITEM(heap
, n
-1) ;
143 PyList_SetSlice(heap
, n
-1, n
, NULL
);
148 returnitem
= PyList_GET_ITEM(heap
, 0);
149 PyList_SET_ITEM(heap
, 0, lastelt
);
150 if (_siftup((PyListObject
*)heap
, 0) == -1) {
151 Py_DECREF(returnitem
);
157 PyDoc_STRVAR(heappop_doc
,
158 "Pop the smallest item off the heap, maintaining the heap invariant.");
161 heapreplace(PyObject
*self
, PyObject
*args
)
163 PyObject
*heap
, *item
, *returnitem
;
165 if (!PyArg_UnpackTuple(args
, "heapreplace", 2, 2, &heap
, &item
))
168 if (!PyList_Check(heap
)) {
169 PyErr_SetString(PyExc_TypeError
, "heap argument must be a list");
173 if (PyList_GET_SIZE(heap
) < 1) {
174 PyErr_SetString(PyExc_IndexError
, "index out of range");
178 returnitem
= PyList_GET_ITEM(heap
, 0);
180 PyList_SET_ITEM(heap
, 0, item
);
181 if (_siftup((PyListObject
*)heap
, 0) == -1) {
182 Py_DECREF(returnitem
);
188 PyDoc_STRVAR(heapreplace_doc
,
189 "Pop and return the current smallest value, and add the new item.\n\
191 This is more efficient than heappop() followed by heappush(), and can be\n\
192 more appropriate when using a fixed-size heap. Note that the value\n\
193 returned may be larger than item! That constrains reasonable uses of\n\
194 this routine unless written as part of a conditional replacement:\n\n\
195 if item > heap[0]:\n\
196 item = heapreplace(heap, item)\n");
199 heapify(PyObject
*self
, PyObject
*heap
)
203 if (!PyList_Check(heap
)) {
204 PyErr_SetString(PyExc_TypeError
, "heap argument must be a list");
208 n
= PyList_GET_SIZE(heap
);
209 /* Transform bottom-up. The largest index there's any point to
210 looking at is the largest with a child index in-range, so must
211 have 2*i + 1 < n, or i < (n-1)/2. If n is even = 2*j, this is
212 (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If
213 n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,
214 and that's again n//2-1.
216 for (i
=n
/2-1 ; i
>=0 ; i
--)
217 if(_siftup((PyListObject
*)heap
, i
) == -1)
223 PyDoc_STRVAR(heapify_doc
,
224 "Transform list into a heap, in-place, in O(len(heap)) time.");
227 nlargest(PyObject
*self
, PyObject
*args
)
229 PyObject
*heap
=NULL
, *elem
, *iterable
, *sol
, *it
, *oldelem
;
232 if (!PyArg_ParseTuple(args
, "nO:nlargest", &n
, &iterable
))
235 it
= PyObject_GetIter(iterable
);
239 heap
= PyList_New(0);
243 for (i
=0 ; i
<n
; i
++ ){
244 elem
= PyIter_Next(it
);
246 if (PyErr_Occurred())
251 if (PyList_Append(heap
, elem
) == -1) {
257 if (PyList_GET_SIZE(heap
) == 0)
260 for (i
=n
/2-1 ; i
>=0 ; i
--)
261 if(_siftup((PyListObject
*)heap
, i
) == -1)
264 sol
= PyList_GET_ITEM(heap
, 0);
266 elem
= PyIter_Next(it
);
268 if (PyErr_Occurred())
273 if (PyObject_RichCompareBool(elem
, sol
, Py_LE
)) {
277 oldelem
= PyList_GET_ITEM(heap
, 0);
278 PyList_SET_ITEM(heap
, 0, elem
);
280 if (_siftup((PyListObject
*)heap
, 0) == -1)
282 sol
= PyList_GET_ITEM(heap
, 0);
285 if (PyList_Sort(heap
) == -1)
287 if (PyList_Reverse(heap
) == -1)
298 PyDoc_STRVAR(nlargest_doc
,
299 "Find the n largest elements in a dataset.\n\
301 Equivalent to: sorted(iterable, reverse=True)[:n]\n");
304 _siftdownmax(PyListObject
*heap
, Py_ssize_t startpos
, Py_ssize_t pos
)
306 PyObject
*newitem
, *parent
;
308 Py_ssize_t parentpos
;
310 assert(PyList_Check(heap
));
311 if (pos
>= PyList_GET_SIZE(heap
)) {
312 PyErr_SetString(PyExc_IndexError
, "index out of range");
316 newitem
= PyList_GET_ITEM(heap
, pos
);
318 /* Follow the path to the root, moving parents down until finding
319 a place newitem fits. */
320 while (pos
> startpos
){
321 parentpos
= (pos
- 1) >> 1;
322 parent
= PyList_GET_ITEM(heap
, parentpos
);
323 cmp
= PyObject_RichCompareBool(newitem
, parent
, Py_LE
);
331 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
332 PyList_SET_ITEM(heap
, pos
, parent
);
335 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
336 PyList_SET_ITEM(heap
, pos
, newitem
);
341 _siftupmax(PyListObject
*heap
, Py_ssize_t pos
)
343 Py_ssize_t startpos
, endpos
, childpos
, rightpos
;
345 PyObject
*newitem
, *tmp
;
347 assert(PyList_Check(heap
));
348 endpos
= PyList_GET_SIZE(heap
);
351 PyErr_SetString(PyExc_IndexError
, "index out of range");
354 newitem
= PyList_GET_ITEM(heap
, pos
);
357 /* Bubble up the smaller child until hitting a leaf. */
358 childpos
= 2*pos
+ 1; /* leftmost child position */
359 while (childpos
< endpos
) {
360 /* Set childpos to index of smaller child. */
361 rightpos
= childpos
+ 1;
362 if (rightpos
< endpos
) {
363 cmp
= PyObject_RichCompareBool(
364 PyList_GET_ITEM(heap
, childpos
),
365 PyList_GET_ITEM(heap
, rightpos
),
374 /* Move the smaller child up. */
375 tmp
= PyList_GET_ITEM(heap
, childpos
);
377 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
378 PyList_SET_ITEM(heap
, pos
, tmp
);
380 childpos
= 2*pos
+ 1;
383 /* The leaf at pos is empty now. Put newitem there, and and bubble
384 it up to its final resting place (by sifting its parents down). */
385 Py_DECREF(PyList_GET_ITEM(heap
, pos
));
386 PyList_SET_ITEM(heap
, pos
, newitem
);
387 return _siftdownmax(heap
, startpos
, pos
);
391 nsmallest(PyObject
*self
, PyObject
*args
)
393 PyObject
*heap
=NULL
, *elem
, *iterable
, *los
, *it
, *oldelem
;
396 if (!PyArg_ParseTuple(args
, "nO:nsmallest", &n
, &iterable
))
399 it
= PyObject_GetIter(iterable
);
403 heap
= PyList_New(0);
407 for (i
=0 ; i
<n
; i
++ ){
408 elem
= PyIter_Next(it
);
410 if (PyErr_Occurred())
415 if (PyList_Append(heap
, elem
) == -1) {
421 n
= PyList_GET_SIZE(heap
);
425 for (i
=n
/2-1 ; i
>=0 ; i
--)
426 if(_siftupmax((PyListObject
*)heap
, i
) == -1)
429 los
= PyList_GET_ITEM(heap
, 0);
431 elem
= PyIter_Next(it
);
433 if (PyErr_Occurred())
438 if (PyObject_RichCompareBool(los
, elem
, Py_LE
)) {
443 oldelem
= PyList_GET_ITEM(heap
, 0);
444 PyList_SET_ITEM(heap
, 0, elem
);
446 if (_siftupmax((PyListObject
*)heap
, 0) == -1)
448 los
= PyList_GET_ITEM(heap
, 0);
452 if (PyList_Sort(heap
) == -1)
463 PyDoc_STRVAR(nsmallest_doc
,
464 "Find the n smallest elements in a dataset.\n\
466 Equivalent to: sorted(iterable)[:n]\n");
468 static PyMethodDef heapq_methods
[] = {
469 {"heappush", (PyCFunction
)heappush
,
470 METH_VARARGS
, heappush_doc
},
471 {"heappop", (PyCFunction
)heappop
,
472 METH_O
, heappop_doc
},
473 {"heapreplace", (PyCFunction
)heapreplace
,
474 METH_VARARGS
, heapreplace_doc
},
475 {"heapify", (PyCFunction
)heapify
,
476 METH_O
, heapify_doc
},
477 {"nlargest", (PyCFunction
)nlargest
,
478 METH_VARARGS
, nlargest_doc
},
479 {"nsmallest", (PyCFunction
)nsmallest
,
480 METH_VARARGS
, nsmallest_doc
},
481 {NULL
, NULL
} /* sentinel */
484 PyDoc_STRVAR(module_doc
,
485 "Heap queue algorithm (a.k.a. priority queue).\n\
487 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
488 all k, counting elements from 0. For the sake of comparison,\n\
489 non-existing elements are considered to be infinite. The interesting\n\
490 property of a heap is that a[0] is always its smallest element.\n\
494 heap = [] # creates an empty heap\n\
495 heappush(heap, item) # pushes a new item on the heap\n\
496 item = heappop(heap) # pops the smallest item from the heap\n\
497 item = heap[0] # smallest item on the heap without popping it\n\
498 heapify(x) # transforms list into a heap, in-place, in linear time\n\
499 item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\
500 # new item; the heap size is unchanged\n\
502 Our API differs from textbook heap algorithms as follows:\n\
504 - We use 0-based indexing. This makes the relationship between the\n\
505 index for a node and the indexes for its children slightly less\n\
506 obvious, but is more suitable since Python uses 0-based indexing.\n\
508 - Our heappop() method returns the smallest item, not the largest.\n\
510 These two make it possible to view the heap as a regular Python list\n\
511 without surprises: heap[0] is the smallest item, and heap.sort()\n\
512 maintains the heap invariant!\n");
515 PyDoc_STRVAR(__about__
,
518 [explanation by François Pinard]\n\
520 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
521 all k, counting elements from 0. For the sake of comparison,\n\
522 non-existing elements are considered to be infinite. The interesting\n\
523 property of a heap is that a[0] is always its smallest element.\n"
525 The strange invariant above is meant to be an efficient memory\n\
526 representation for a tournament. The numbers below are `k', not a[k]:\n\
534 7 8 9 10 11 12 13 14\n\
536 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30\n\
539 In the tree above, each cell `k' is topping `2*k+1' and `2*k+2'. In\n\
540 an usual binary tournament we see in sports, each cell is the winner\n\
541 over the two cells it tops, and we can trace the winner down the tree\n\
542 to see all opponents s/he had. However, in many computer applications\n\
543 of such tournaments, we do not need to trace the history of a winner.\n\
544 To be more memory efficient, when a winner is promoted, we try to\n\
545 replace it by something else at a lower level, and the rule becomes\n\
546 that a cell and the two cells it tops contain three different items,\n\
547 but the top cell \"wins\" over the two topped cells.\n"
549 If this heap invariant is protected at all time, index 0 is clearly\n\
550 the overall winner. The simplest algorithmic way to remove it and\n\
551 find the \"next\" winner is to move some loser (let's say cell 30 in the\n\
552 diagram above) into the 0 position, and then percolate this new 0 down\n\
553 the tree, exchanging values, until the invariant is re-established.\n\
554 This is clearly logarithmic on the total number of items in the tree.\n\
555 By iterating over all items, you get an O(n ln n) sort.\n"
557 A nice feature of this sort is that you can efficiently insert new\n\
558 items while the sort is going on, provided that the inserted items are\n\
559 not \"better\" than the last 0'th element you extracted. This is\n\
560 especially useful in simulation contexts, where the tree holds all\n\
561 incoming events, and the \"win\" condition means the smallest scheduled\n\
562 time. When an event schedule other events for execution, they are\n\
563 scheduled into the future, so they can easily go into the heap. So, a\n\
564 heap is a good structure for implementing schedulers (this is what I\n\
565 used for my MIDI sequencer :-).\n"
567 Various structures for implementing schedulers have been extensively\n\
568 studied, and heaps are good for this, as they are reasonably speedy,\n\
569 the speed is almost constant, and the worst case is not much different\n\
570 than the average case. However, there are other representations which\n\
571 are more efficient overall, yet the worst cases might be terrible.\n"
573 Heaps are also very useful in big disk sorts. You most probably all\n\
574 know that a big sort implies producing \"runs\" (which are pre-sorted\n\
575 sequences, which size is usually related to the amount of CPU memory),\n\
576 followed by a merging passes for these runs, which merging is often\n\
577 very cleverly organised[1]. It is very important that the initial\n\
578 sort produces the longest runs possible. Tournaments are a good way\n\
579 to that. If, using all the memory available to hold a tournament, you\n\
580 replace and percolate items that happen to fit the current run, you'll\n\
581 produce runs which are twice the size of the memory for random input,\n\
582 and much better for input fuzzily ordered.\n"
584 Moreover, if you output the 0'th item on disk and get an input which\n\
585 may not fit in the current tournament (because the value \"wins\" over\n\
586 the last output value), it cannot fit in the heap, so the size of the\n\
587 heap decreases. The freed memory could be cleverly reused immediately\n\
588 for progressively building a second heap, which grows at exactly the\n\
589 same rate the first heap is melting. When the first heap completely\n\
590 vanishes, you switch heaps and start a new run. Clever and quite\n\
593 In a word, heaps are useful memory structures to know. I use them in\n\
594 a few applications, and I think it is good to keep a `heap' module\n\
597 --------------------\n\
598 [1] The disk balancing algorithms which are current, nowadays, are\n\
599 more annoying than clever, and this is a consequence of the seeking\n\
600 capabilities of the disks. On devices which cannot seek, like big\n\
601 tape drives, the story was quite different, and one had to be very\n\
602 clever to ensure (far in advance) that each tape movement will be the\n\
603 most effective possible (that is, will best participate at\n\
604 \"progressing\" the merge). Some tapes were even able to read\n\
605 backwards, and this was also used to avoid the rewinding time.\n\
606 Believe me, real good tape sorts were quite spectacular to watch!\n\
607 From all times, sorting has always been a Great Art! :-)\n");
614 m
= Py_InitModule3("_heapq", heapq_methods
, module_doc
);
617 PyModule_AddObject(m
, "__about__", PyString_FromString(__about__
));