Lines Matching refs:heap
36 _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
42 assert(PyList_Check(heap));
43 size = PyList_GET_SIZE(heap);
51 newitem = PyList_GET_ITEM(heap, pos);
54 parent = PyList_GET_ITEM(heap, parentpos);
58 if (size != PyList_GET_SIZE(heap)) {
65 parent = PyList_GET_ITEM(heap, parentpos);
66 newitem = PyList_GET_ITEM(heap, pos);
67 PyList_SET_ITEM(heap, parentpos, newitem);
68 PyList_SET_ITEM(heap, pos, parent);
75 _siftup(PyListObject *heap, Py_ssize_t pos)
81 assert(PyList_Check(heap));
82 endpos = PyList_GET_SIZE(heap);
97 PyList_GET_ITEM(heap, childpos),
98 PyList_GET_ITEM(heap, rightpos));
103 if (endpos != PyList_GET_SIZE(heap)) {
110 tmp1 = PyList_GET_ITEM(heap, childpos);
111 tmp2 = PyList_GET_ITEM(heap, pos);
112 PyList_SET_ITEM(heap, childpos, tmp2);
113 PyList_SET_ITEM(heap, pos, tmp1);
117 return _siftdown(heap, startpos, pos);
123 PyObject *heap, *item;
125 if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item))
128 if (!PyList_Check(heap)) {
129 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
133 if (PyList_Append(heap, item) == -1)
136 if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1)
143 "heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant.");
146 heappop(PyObject *self, PyObject *heap)
151 if (!PyList_Check(heap)) {
152 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
156 /* # raises appropriate IndexError if heap is empty */
157 n = PyList_GET_SIZE(heap);
163 lastelt = PyList_GET_ITEM(heap, n-1) ;
165 PyList_SetSlice(heap, n-1, n, NULL);
170 returnitem = PyList_GET_ITEM(heap, 0);
171 PyList_SET_ITEM(heap, 0, lastelt);
172 if (_siftup((PyListObject *)heap, 0) == -1) {
180 "Pop the smallest item off the heap, maintaining the heap invariant.");
185 PyObject *heap, *item, *returnitem;
187 if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item))
190 if (!PyList_Check(heap)) {
191 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
195 if (PyList_GET_SIZE(heap) < 1) {
200 returnitem = PyList_GET_ITEM(heap, 0);
202 PyList_SET_ITEM(heap, 0, item);
203 if (_siftup((PyListObject *)heap, 0) == -1) {
211 "heapreplace(heap, item) -> value. Pop and return the current smallest value, and add the new item.\n\
214 more appropriate when using a fixed-size heap. Note that the value\n\
217 if item > heap[0]:\n\
218 item = heapreplace(heap, item)\n");
223 PyObject *heap, *item, *returnitem;
226 if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item))
229 if (!PyList_Check(heap)) {
230 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
234 if (PyList_GET_SIZE(heap) < 1) {
239 cmp = cmp_lt(PyList_GET_ITEM(heap, 0), item);
247 if (PyList_GET_SIZE(heap) == 0) {
252 returnitem = PyList_GET_ITEM(heap, 0);
254 PyList_SET_ITEM(heap, 0, item);
255 if (_siftup((PyListObject *)heap, 0) == -1) {
263 "heappushpop(heap, item) -> value. Push item on the heap, then pop and return the smallest item\n\
264 from the heap. The combined action runs more efficiently than\n\
268 heapify(PyObject *self, PyObject *heap)
272 if (!PyList_Check(heap)) {
273 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
277 n = PyList_GET_SIZE(heap);
286 if(_siftup((PyListObject *)heap, i) == -1)
293 "Transform list into a heap, in-place, in O(len(heap)) time.");
298 PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem;
309 heap = PyList_New(0);
310 if (heap == NULL)
321 if (PyList_Append(heap, elem) == -1) {
327 if (PyList_GET_SIZE(heap) == 0)
331 if(_siftup((PyListObject *)heap, i) == -1)
334 sol = PyList_GET_ITEM(heap, 0);
352 oldelem = PyList_GET_ITEM(heap, 0);
353 PyList_SET_ITEM(heap, 0, elem);
355 if (_siftup((PyListObject *)heap, 0) == -1)
357 sol = PyList_GET_ITEM(heap, 0);
360 if (PyList_Sort(heap) == -1)
362 if (PyList_Reverse(heap) == -1)
365 return heap;
369 Py_XDECREF(heap);
379 _siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
385 assert(PyList_Check(heap));
386 if (pos >= PyList_GET_SIZE(heap)) {
391 newitem = PyList_GET_ITEM(heap, pos);
397 parent = PyList_GET_ITEM(heap, parentpos);
406 Py_DECREF(PyList_GET_ITEM(heap, pos));
407 PyList_SET_ITEM(heap, pos, parent);
410 Py_DECREF(PyList_GET_ITEM(heap, pos));
411 PyList_SET_ITEM(heap, pos, newitem);
416 _siftupmax(PyListObject *heap, Py_ssize_t pos)
422 assert(PyList_Check(heap));
423 endpos = PyList_GET_SIZE(heap);
429 newitem = PyList_GET_ITEM(heap, pos);
440 PyList_GET_ITEM(heap, rightpos),
441 PyList_GET_ITEM(heap, childpos));
450 tmp = PyList_GET_ITEM(heap, childpos);
452 Py_DECREF(PyList_GET_ITEM(heap, pos));
453 PyList_SET_ITEM(heap, pos, tmp);
459 Py_DECREF(PyList_GET_ITEM(heap, pos));
460 PyList_SET_ITEM(heap, pos, newitem);
461 return _siftdownmax(heap, startpos, pos);
467 PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem;
478 heap = PyList_New(0);
479 if (heap == NULL)
490 if (PyList_Append(heap, elem) == -1) {
496 n = PyList_GET_SIZE(heap);
501 if(_siftupmax((PyListObject *)heap, i) == -1)
504 los = PyList_GET_ITEM(heap, 0);
523 oldelem = PyList_GET_ITEM(heap, 0);
524 PyList_SET_ITEM(heap, 0, elem);
526 if (_siftupmax((PyListObject *)heap, 0) == -1)
528 los = PyList_GET_ITEM(heap, 0);
532 if (PyList_Sort(heap) == -1)
535 return heap;
539 Py_XDECREF(heap);
567 "Heap queue algorithm (a.k.a. priority queue).\n\
572 property of a heap is that a[0] is always its smallest element.\n\
576 heap = [] # creates an empty heap\n\
577 heappush(heap, item) # pushes a new item on the heap\n\
578 item = heappop(heap) # pops the smallest item from the heap\n\
579 item = heap[0] # smallest item on the heap without popping it\n\
580 heapify(x) # transforms list into a heap, in-place, in linear time\n\
581 item = heapreplace(heap
582 # new item; the heap size is unchanged\n\
584 Our API differs from textbook heap algorithms as follows:\n\
592 These two make it possible to view the heap as a regular Python list\n\
593 without surprises: heap[0] is the smallest item, and heap.sort()\n\
594 maintains the heap invariant!\n");
598 "Heap queues\n\
605 property of a heap is that a[0] is always its smallest element.\n"
631 If this heap invariant is protected at all time, index 0 is clearly\n\
645 scheduled into the future, so they can easily go into the heap. So, a\n\
646 heap is a good structure for implementing schedulers (this is what I\n\
668 the last output value), it cannot fit in the heap, so the size of the\n\
669 heap decreases. The freed memory could be cleverly reused immediately\n\
670 for progressively building a second heap, which grows at exactly the\n\
671 same rate the first heap is melting. When the first heap completely\n\
676 a few applications, and I think it is good to keep a `heap' module\n\
