Move element at pos down to a leaf by repeatedly moving the smaller child up.
(self, pos)
| 134 | self._siftdown(pos) |
| 135 | |
| 136 | def _siftup(self, pos): |
| 137 | """Move element at pos down to a leaf by repeatedly moving the smaller |
| 138 | child up.""" |
| 139 | h, d = self.h, self.d |
| 140 | elt = h[pos] |
| 141 | # Continue until element is in a leaf |
| 142 | end_pos = len(h) |
| 143 | left_pos = (pos << 1) + 1 |
| 144 | while left_pos < end_pos: |
| 145 | # Left child is guaranteed to exist by loop predicate |
| 146 | left = h[left_pos] |
| 147 | try: |
| 148 | right_pos = left_pos + 1 |
| 149 | right = h[right_pos] |
| 150 | # Out-of-place, swap with left unless right is smaller |
| 151 | if right < left: |
| 152 | h[pos], h[right_pos] = right, elt |
| 153 | pos, right_pos = right_pos, pos |
| 154 | d[elt], d[right] = pos, right_pos |
| 155 | else: |
| 156 | h[pos], h[left_pos] = left, elt |
| 157 | pos, left_pos = left_pos, pos |
| 158 | d[elt], d[left] = pos, left_pos |
| 159 | except IndexError: |
| 160 | # Left leaf is the end of the heap, swap |
| 161 | h[pos], h[left_pos] = left, elt |
| 162 | pos, left_pos = left_pos, pos |
| 163 | d[elt], d[left] = pos, left_pos |
| 164 | # Update left_pos |
| 165 | left_pos = (pos << 1) + 1 |
| 166 | return pos |
| 167 | |
| 168 | def _siftdown(self, pos): |
| 169 | """Restore invariant by repeatedly replacing out-of-place element with |