Lines Matching refs:heap
25 siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
31 assert(PyList_Check(heap));
32 size = PyList_GET_SIZE(heap);
40 arr = _PyList_ITEMS(heap);
52 if (size != PyList_GET_SIZE(heap)) {
59 arr = _PyList_ITEMS(heap);
70 siftup(PyListObject *heap, Py_ssize_t pos)
76 assert(PyList_Check(heap));
77 endpos = PyList_GET_SIZE(heap);
85 arr = _PyList_ITEMS(heap);
101 arr = _PyList_ITEMS(heap); /* arr may have changed */
102 if (endpos != PyList_GET_SIZE(heap)) {
116 return siftdown(heap, startpos, pos);
122 heap: object(subclass_of='&PyList_Type')
126 Push item onto heap, maintaining the heap invariant.
130 _heapq_heappush_impl(PyObject *module, PyObject *heap, PyObject *item)
133 if (PyList_Append(heap, item))
136 if (siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1))
142 heappop_internal(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t))
147 /* raises IndexError if the heap is empty */
148 n = PyList_GET_SIZE(heap);
154 lastelt = PyList_GET_ITEM(heap, n-1) ;
156 if (PyList_SetSlice(heap, n-1, n, NULL)) {
164 returnitem = PyList_GET_ITEM(heap, 0);
165 PyList_SET_ITEM(heap, 0, lastelt);
166 if (siftup_func((PyListObject *)heap, 0)) {
176 heap: object(subclass_of='&PyList_Type')
179 Pop the smallest item off the heap, maintaining the heap invariant.
183 _heapq_heappop_impl(PyObject *module, PyObject *heap)
186 return heappop_internal(heap, siftup);
190 heapreplace_internal(PyObject *heap, PyObject *item, int siftup_func(PyListObject *, Py_ssize_t))
194 if (PyList_GET_SIZE(heap) == 0) {
199 returnitem = PyList_GET_ITEM(heap, 0);
201 PyList_SET_ITEM(heap, 0, item);
202 if (siftup_func((PyListObject *)heap, 0)) {
213 heap: object(subclass_of='&PyList_Type')
220 more appropriate when using a fixed-size heap. Note that the value
224 if item > heap[0]:
225 item = heapreplace(heap, item)
229 _heapq_heapreplace_impl(PyObject *module, PyObject *heap, PyObject *item)
232 return heapreplace_internal(heap, item, siftup);
238 heap: object(subclass_of='&PyList_Type')
242 Push item on the heap, then pop and return the smallest item from the heap.
249 _heapq_heappushpop_impl(PyObject *module, PyObject *heap, PyObject *item)
255 if (PyList_GET_SIZE(heap) == 0) {
260 PyObject* top = PyList_GET_ITEM(heap, 0);
271 if (PyList_GET_SIZE(heap) == 0) {
276 returnitem = PyList_GET_ITEM(heap, 0);
278 PyList_SET_ITEM(heap, 0, item);
279 if (siftup((PyListObject *)heap, 0)) {
301 Build-up a heap in O(n) time by performing siftup() operations
314 the same heap. The only difference is that the traversal
319 cache_friendly_heapify(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t))
323 m = PyList_GET_SIZE(heap) >> 1; /* index of first childless node */
330 if (siftup_func((PyListObject *)heap, j))
341 if (siftup_func((PyListObject *)heap, j))
352 heapify_internal(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t))
360 n = PyList_GET_SIZE(heap);
362 return cache_friendly_heapify(heap, siftup_func);
372 if (siftup_func((PyListObject *)heap, i))
380 heap: object(subclass_of='&PyList_Type')
383 Transform list into a heap, in-place, in O(len(heap)) time.
387 _heapq_heapify_impl(PyObject *module, PyObject *heap)
390 return heapify_internal(heap, siftup);
394 siftdown_max(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
400 assert(PyList_Check(heap));
401 size = PyList_GET_SIZE(heap);
409 arr = _PyList_ITEMS(heap);
421 if (size != PyList_GET_SIZE(heap)) {
428 arr = _PyList_ITEMS(heap);
439 siftup_max(PyListObject *heap, Py_ssize_t pos)
445 assert(PyList_Check(heap));
446 endpos = PyList_GET_SIZE(heap);
454 arr = _PyList_ITEMS(heap);
470 arr = _PyList_ITEMS(heap); /* arr may have changed */
471 if (endpos != PyList_GET_SIZE(heap)) {
485 return siftdown_max(heap, startpos, pos);
492 heap: object(subclass_of='&PyList_Type')
499 _heapq__heappop_max_impl(PyObject *module, PyObject *heap)
502 return heappop_internal(heap, siftup_max);
508 heap: object(subclass_of='&PyList_Type')
516 _heapq__heapreplace_max_impl(PyObject *module, PyObject *heap,
520 return heapreplace_internal(heap, item, siftup_max);
526 heap: object(subclass_of='&PyList_Type')
533 _heapq__heapify_max_impl(PyObject *module, PyObject *heap)
536 return heapify_internal(heap, siftup_max);
557 property of a heap is that a[0] is always its smallest element.\n\
561 heap = [] # creates an empty heap\n\
562 heappush(heap, item) # pushes a new item on the heap\n\
563 item = heappop(heap) # pops the smallest item from the heap\n\
564 item = heap[0] # smallest item on the heap without popping it\n\
565 heapify(x) # transforms list into a heap, in-place, in linear time\n\
566 item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\
567 # new item; the heap size is unchanged\n\
569 Our API differs from textbook heap algorithms as follows:\n\
577 These two make it possible to view the heap as a regular Python list\n\
578 without surprises: heap[0] is the smallest item, and heap.sort()\n\
579 maintains the heap invariant!\n");
590 property of a heap is that a[0] is always its smallest element.\n"
616 If this heap invariant is protected at all time, index 0 is clearly\n\
630 scheduled into the future, so they can easily go into the heap. So, a\n\
631 heap is a good structure for implementing schedulers (this is what I\n\
653 the last output value), it cannot fit in the heap, so the size of the\n\
654 heap decreases. The freed memory could be cleverly reused immediately\n\
655 for progressively building a second heap, which grows at exactly the\n\
656 same rate the first heap is melting. When the first heap completely\n\
661 a few applications, and I think it is good to keep a `heap' module\n\