Restore invariant by repeatedly replacing out-of-place element with its parent.
(self, pos)
| 166 | return pos |
| 167 | |
| 168 | def _siftdown(self, pos): |
| 169 | """Restore invariant by repeatedly replacing out-of-place element with |
| 170 | its parent.""" |
| 171 | h, d = self.h, self.d |
| 172 | elt = h[pos] |
| 173 | # Continue until element is at root |
| 174 | while pos > 0: |
| 175 | parent_pos = (pos - 1) >> 1 |
| 176 | parent = h[parent_pos] |
| 177 | if parent > elt: |
| 178 | # Swap out-of-place element with parent |
| 179 | h[parent_pos], h[pos] = elt, parent |
| 180 | parent_pos, pos = pos, parent_pos |
| 181 | d[elt] = pos |
| 182 | d[parent] = parent_pos |
| 183 | else: |
| 184 | # Invariant is satisfied |
| 185 | break |
| 186 | return pos |