Select the root and sift down until min-heap property is met. While a favorite child exists, and that child is smaller than the parent, swap them (sift down). Best Case: O(1), item is inserted at correct position, no swaps needed Worst Case: O(logn), ite
(self)
| 92 | return None |
| 93 | |
| 94 | def heapify_down(self): |
| 95 | """ |
| 96 | Select the root and sift down until min-heap property is met. |
| 97 | |
| 98 | While a favorite child exists, and that child is smaller |
| 99 | than the parent, swap them (sift down). |
| 100 | |
| 101 | Best Case: O(1), item is inserted at correct position, no swaps needed |
| 102 | Worst Case: O(logn), item needs to be swapped throughout all levels of tree |
| 103 | """ |
| 104 | cur = 0 # start at the root |
| 105 | fav = self.favorite(cur) # determine favorite child |
| 106 | while self.queue[fav] is not None: |
| 107 | if self.queue[cur] > self.queue[fav]: |
| 108 | # Swap (sift down) and update parent:favorite relation |
| 109 | fav = self.favorite(cur) |
| 110 | self.queue[cur], self.queue[fav] = self.queue[fav], self.queue[cur] |
| 111 | cur = fav |
| 112 | else: |
| 113 | return |
| 114 | |
| 115 | # TODO: Is this necessary? |
| 116 | @staticmethod |