Lines Matching refs:pos
239 # 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
242 def _siftdown(heap, startpos, pos):
243 newitem = heap[pos]
246 while pos > startpos:
247 parentpos = (pos - 1) >> 1
250 heap[pos] = parent
251 pos = parentpos
254 heap[pos] = newitem
256 # The child indices of heap index pos are already heaps, and we want to make
257 # a heap at index pos too. We do this by bubbling the smaller child of
258 # pos up (and so on with that child's children, etc) until hitting a leaf,
259 # then using _siftdown to move the oddball originally at index pos into place.
261 # We *could* break out of the loop as soon as we find a pos where newitem <=
295 def _siftup(heap, pos):
297 startpos = pos
298 newitem = heap[pos]
300 childpos = 2*pos + 1 # leftmost child position
307 heap[pos] = heap[childpos]
308 pos = childpos
309 childpos = 2*pos + 1
310 # The leaf at pos is empty now. Put newitem there, and bubble it up
312 heap[pos] = newitem
313 _siftdown(heap, startpos, pos)
315 def _siftdown_max(heap, startpos, pos):
317 newitem = heap[pos]
320 while pos > startpos:
321 parentpos = (pos - 1) >> 1
324 heap[pos] = parent
325 pos = parentpos
328 heap[pos] = newitem
330 def _siftup_max(heap, pos):
333 startpos = pos
334 newitem = heap[pos]
336 childpos = 2*pos + 1 # leftmost child position
343 heap[pos] = heap[childpos]
344 pos = childpos
345 childpos = 2*pos + 1
346 # The leaf at pos is empty now. Put newitem there, and bubble it up
348 heap[pos] = newitem
349 _siftdown_max(heap, startpos, pos)
