Lines Matching refs:heap
36 _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) in _siftdown() argument
42 assert(PyList_Check(heap)); in _siftdown()
43 size = PyList_GET_SIZE(heap); in _siftdown()
51 newitem = PyList_GET_ITEM(heap, pos); in _siftdown()
54 parent = PyList_GET_ITEM(heap, parentpos); in _siftdown()
58 if (size != PyList_GET_SIZE(heap)) { in _siftdown()
65 parent = PyList_GET_ITEM(heap, parentpos); in _siftdown()
66 newitem = PyList_GET_ITEM(heap, pos); in _siftdown()
67 PyList_SET_ITEM(heap, parentpos, newitem); in _siftdown()
68 PyList_SET_ITEM(heap, pos, parent); in _siftdown()
75 _siftup(PyListObject *heap, Py_ssize_t pos) in _siftup() argument
81 assert(PyList_Check(heap)); in _siftup()
82 endpos = PyList_GET_SIZE(heap); in _siftup()
97 PyList_GET_ITEM(heap, childpos), in _siftup()
98 PyList_GET_ITEM(heap, rightpos)); in _siftup()
103 if (endpos != PyList_GET_SIZE(heap)) { in _siftup()
110 tmp1 = PyList_GET_ITEM(heap, childpos); in _siftup()
111 tmp2 = PyList_GET_ITEM(heap, pos); in _siftup()
112 PyList_SET_ITEM(heap, childpos, tmp2); in _siftup()
113 PyList_SET_ITEM(heap, pos, tmp1); in _siftup()
117 return _siftdown(heap, startpos, pos); in _siftup()
123 PyObject *heap, *item; in heappush() local
125 if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item)) in heappush()
128 if (!PyList_Check(heap)) { in heappush()
133 if (PyList_Append(heap, item) == -1) in heappush()
136 if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1) in heappush()
146 heappop(PyObject *self, PyObject *heap) in heappop() argument
151 if (!PyList_Check(heap)) { in heappop()
157 n = PyList_GET_SIZE(heap); in heappop()
163 lastelt = PyList_GET_ITEM(heap, n-1) ; in heappop()
165 PyList_SetSlice(heap, n-1, n, NULL); in heappop()
170 returnitem = PyList_GET_ITEM(heap, 0); in heappop()
171 PyList_SET_ITEM(heap, 0, lastelt); in heappop()
172 if (_siftup((PyListObject *)heap, 0) == -1) { in heappop()
185 PyObject *heap, *item, *returnitem; in heapreplace() local
187 if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item)) in heapreplace()
190 if (!PyList_Check(heap)) { in heapreplace()
195 if (PyList_GET_SIZE(heap) < 1) { in heapreplace()
200 returnitem = PyList_GET_ITEM(heap, 0); in heapreplace()
202 PyList_SET_ITEM(heap, 0, item); in heapreplace()
203 if (_siftup((PyListObject *)heap, 0) == -1) { in heapreplace()
223 PyObject *heap, *item, *returnitem; in heappushpop() local
226 if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item)) in heappushpop()
229 if (!PyList_Check(heap)) { in heappushpop()
234 if (PyList_GET_SIZE(heap) < 1) { in heappushpop()
239 cmp = cmp_lt(PyList_GET_ITEM(heap, 0), item); in heappushpop()
247 if (PyList_GET_SIZE(heap) == 0) { in heappushpop()
252 returnitem = PyList_GET_ITEM(heap, 0); in heappushpop()
254 PyList_SET_ITEM(heap, 0, item); in heappushpop()
255 if (_siftup((PyListObject *)heap, 0) == -1) { in heappushpop()
268 heapify(PyObject *self, PyObject *heap) in heapify() argument
272 if (!PyList_Check(heap)) { in heapify()
277 n = PyList_GET_SIZE(heap); in heapify()
286 if(_siftup((PyListObject *)heap, i) == -1) in heapify()
298 PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem; in nlargest() local
309 heap = PyList_New(0); in nlargest()
310 if (heap == NULL) in nlargest()
321 if (PyList_Append(heap, elem) == -1) { in nlargest()
327 if (PyList_GET_SIZE(heap) == 0) in nlargest()
331 if(_siftup((PyListObject *)heap, i) == -1) in nlargest()
334 sol = PyList_GET_ITEM(heap, 0); in nlargest()
352 oldelem = PyList_GET_ITEM(heap, 0); in nlargest()
353 PyList_SET_ITEM(heap, 0, elem); in nlargest()
355 if (_siftup((PyListObject *)heap, 0) == -1) in nlargest()
357 sol = PyList_GET_ITEM(heap, 0); in nlargest()
360 if (PyList_Sort(heap) == -1) in nlargest()
362 if (PyList_Reverse(heap) == -1) in nlargest()
365 return heap; in nlargest()
369 Py_XDECREF(heap); in nlargest()
379 _siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) in _siftdownmax() argument
385 assert(PyList_Check(heap)); in _siftdownmax()
386 if (pos >= PyList_GET_SIZE(heap)) { in _siftdownmax()
391 newitem = PyList_GET_ITEM(heap, pos); in _siftdownmax()
397 parent = PyList_GET_ITEM(heap, parentpos); in _siftdownmax()
406 Py_DECREF(PyList_GET_ITEM(heap, pos)); in _siftdownmax()
407 PyList_SET_ITEM(heap, pos, parent); in _siftdownmax()
410 Py_DECREF(PyList_GET_ITEM(heap, pos)); in _siftdownmax()
411 PyList_SET_ITEM(heap, pos, newitem); in _siftdownmax()
416 _siftupmax(PyListObject *heap, Py_ssize_t pos) in _siftupmax() argument
422 assert(PyList_Check(heap)); in _siftupmax()
423 endpos = PyList_GET_SIZE(heap); in _siftupmax()
429 newitem = PyList_GET_ITEM(heap, pos); in _siftupmax()
440 PyList_GET_ITEM(heap, rightpos), in _siftupmax()
441 PyList_GET_ITEM(heap, childpos)); in _siftupmax()
450 tmp = PyList_GET_ITEM(heap, childpos); in _siftupmax()
452 Py_DECREF(PyList_GET_ITEM(heap, pos)); in _siftupmax()
453 PyList_SET_ITEM(heap, pos, tmp); in _siftupmax()
459 Py_DECREF(PyList_GET_ITEM(heap, pos)); in _siftupmax()
460 PyList_SET_ITEM(heap, pos, newitem); in _siftupmax()
461 return _siftdownmax(heap, startpos, pos); in _siftupmax()
467 PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem; in nsmallest() local
478 heap = PyList_New(0); in nsmallest()
479 if (heap == NULL) in nsmallest()
490 if (PyList_Append(heap, elem) == -1) { in nsmallest()
496 n = PyList_GET_SIZE(heap); in nsmallest()
501 if(_siftupmax((PyListObject *)heap, i) == -1) in nsmallest()
504 los = PyList_GET_ITEM(heap, 0); in nsmallest()
523 oldelem = PyList_GET_ITEM(heap, 0); in nsmallest()
524 PyList_SET_ITEM(heap, 0, elem); in nsmallest()
526 if (_siftupmax((PyListObject *)heap, 0) == -1) in nsmallest()
528 los = PyList_GET_ITEM(heap, 0); in nsmallest()
532 if (PyList_Sort(heap) == -1) in nsmallest()
535 return heap; in nsmallest()
539 Py_XDECREF(heap); in nsmallest()