>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12] >>> heapify(array, len(array) // 2, len(array))
(array: list, index: int, heap_size: int)
| 37 | |
| 38 | |
| 39 | def heapify(array: list, index: int, heap_size: int) -> None: # Max Heap |
| 40 | """ |
| 41 | >>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12] |
| 42 | >>> heapify(array, len(array) // 2, len(array)) |
| 43 | """ |
| 44 | largest = index |
| 45 | left_index = 2 * index + 1 # Left Node |
| 46 | right_index = 2 * index + 2 # Right Node |
| 47 | |
| 48 | if left_index < heap_size and array[largest] < array[left_index]: |
| 49 | largest = left_index |
| 50 | |
| 51 | if right_index < heap_size and array[largest] < array[right_index]: |
| 52 | largest = right_index |
| 53 | |
| 54 | if largest != index: |
| 55 | array[index], array[largest] = array[largest], array[index] |
| 56 | heapify(array, largest, heap_size) |
| 57 | |
| 58 | |
| 59 | def heap_sort(array: list) -> list: |