| 219 | # is the index of a leaf with a possibly out-of-order value. Restore the |
| 220 | # heap invariant. |
| 221 | def _siftdown(heap, startpos, pos): |
| 222 | newitem = heap[pos] |
| 223 | # Follow the path to the root, moving parents down until finding a place |
| 224 | # newitem fits. |
| 225 | while pos > startpos: |
| 226 | parentpos = (pos - 1) >> 1 |
| 227 | parent = heap[parentpos] |
| 228 | if newitem < parent: |
| 229 | heap[pos] = parent |
| 230 | pos = parentpos |
| 231 | continue |
| 232 | break |
| 233 | heap[pos] = newitem |
| 234 | |
| 235 | # The child indices of heap index pos are already heaps, and we want to make |
| 236 | # a heap at index pos too. We do this by bubbling the smaller child of |