correct a single violation of the heap property in a subtree's root. It is the function that is responsible for restoring the property of Max heap i.e the maximum element is always at top.
(self, index: int)
| 109 | return None |
| 110 | |
| 111 | def max_heapify(self, index: int) -> None: |
| 112 | """ |
| 113 | correct a single violation of the heap property in a subtree's root. |
| 114 | |
| 115 | It is the function that is responsible for restoring the property |
| 116 | of Max heap i.e the maximum element is always at top. |
| 117 | """ |
| 118 | if index < self.heap_size: |
| 119 | violation: int = index |
| 120 | left_child = self.left_child_idx(index) |
| 121 | right_child = self.right_child_idx(index) |
| 122 | # check which child is larger than its parent |
| 123 | if left_child is not None and self.h[left_child] > self.h[violation]: |
| 124 | violation = left_child |
| 125 | if right_child is not None and self.h[right_child] > self.h[violation]: |
| 126 | violation = right_child |
| 127 | # if violation indeed exists |
| 128 | if violation != index: |
| 129 | # swap to fix the violation |
| 130 | self.h[violation], self.h[index] = self.h[index], self.h[violation] |
| 131 | # fix the subsequent violation recursively if any |
| 132 | self.max_heapify(violation) |
| 133 | |
| 134 | def build_max_heap(self, collection: Iterable[T]) -> None: |
| 135 | """ |
no test coverage detected