>>> heap_sort([4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12]) [1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79] >>> heap_sort([-2, -11, 0, 0, 0, 87, 45, -69, 78, 12, 10, 103, 89, 52]) [-69, -11, -2, 0, 0, 0, 10, 12, 45, 52, 78, 87, 89, 103] >>> heap_sort(['b',
(array: list)
| 57 | |
| 58 | |
| 59 | def heap_sort(array: list) -> list: |
| 60 | """ |
| 61 | >>> heap_sort([4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12]) |
| 62 | [1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79] |
| 63 | >>> heap_sort([-2, -11, 0, 0, 0, 87, 45, -69, 78, 12, 10, 103, 89, 52]) |
| 64 | [-69, -11, -2, 0, 0, 0, 10, 12, 45, 52, 78, 87, 89, 103] |
| 65 | >>> heap_sort(['b', 'd', 'e', 'f', 'g', 'p', 'x', 'z', 'b', 's', 'e', 'u', 'v']) |
| 66 | ['b', 'b', 'd', 'e', 'e', 'f', 'g', 'p', 's', 'u', 'v', 'x', 'z'] |
| 67 | >>> heap_sort([6.2, -45.54, 8465.20, 758.56, -457.0, 0, 1, 2.879, 1.7, 11.7]) |
| 68 | [-457.0, -45.54, 0, 1, 1.7, 2.879, 6.2, 11.7, 758.56, 8465.2] |
| 69 | """ |
| 70 | n = len(array) |
| 71 | |
| 72 | for i in range(n // 2, -1, -1): |
| 73 | heapify(array, i, n) |
| 74 | |
| 75 | for i in range(n - 1, 0, -1): |
| 76 | array[i], array[0] = array[0], array[i] |
| 77 | heapify(array, 0, i) |
| 78 | |
| 79 | return array |
| 80 | |
| 81 | |
| 82 | def median_of_3( |