:param unsorted: unsorted list containing integers numbers :param index: index :param heap_size: size of the heap :return: None >>> unsorted = [1, 4, 3, 5, 2] >>> heapify(unsorted, 0, len(unsorted)) >>> unsorted [4, 5, 3, 1, 2] >>> heapify(unsorted, 0, len(unsort
(unsorted: list[int], index: int, heap_size: int)
| 4 | |
| 5 | |
| 6 | def heapify(unsorted: list[int], index: int, heap_size: int) -> None: |
| 7 | """ |
| 8 | :param unsorted: unsorted list containing integers numbers |
| 9 | :param index: index |
| 10 | :param heap_size: size of the heap |
| 11 | :return: None |
| 12 | >>> unsorted = [1, 4, 3, 5, 2] |
| 13 | >>> heapify(unsorted, 0, len(unsorted)) |
| 14 | >>> unsorted |
| 15 | [4, 5, 3, 1, 2] |
| 16 | >>> heapify(unsorted, 0, len(unsorted)) |
| 17 | >>> unsorted |
| 18 | [5, 4, 3, 1, 2] |
| 19 | """ |
| 20 | largest = index |
| 21 | left_index = 2 * index + 1 |
| 22 | right_index = 2 * index + 2 |
| 23 | if left_index < heap_size and unsorted[left_index] > unsorted[largest]: |
| 24 | largest = left_index |
| 25 | |
| 26 | if right_index < heap_size and unsorted[right_index] > unsorted[largest]: |
| 27 | largest = right_index |
| 28 | |
| 29 | if largest != index: |
| 30 | unsorted[largest], unsorted[index] = (unsorted[index], unsorted[largest]) |
| 31 | heapify(unsorted, largest, heap_size) |
| 32 | |
| 33 | |
| 34 | def heap_sort(unsorted: list[int]) -> list[int]: |