A pure Python implementation of the heap sort algorithm :param collection: a mutable ordered collection of heterogeneous comparable items :return: the same collection ordered by ascending Examples: >>> heap_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> heap_sort([]) []
(unsorted: list[int])
| 32 | |
| 33 | |
| 34 | def heap_sort(unsorted: list[int]) -> list[int]: |
| 35 | """ |
| 36 | A pure Python implementation of the heap sort algorithm |
| 37 | |
| 38 | :param collection: a mutable ordered collection of heterogeneous comparable items |
| 39 | :return: the same collection ordered by ascending |
| 40 | |
| 41 | Examples: |
| 42 | >>> heap_sort([0, 5, 3, 2, 2]) |
| 43 | [0, 2, 2, 3, 5] |
| 44 | >>> heap_sort([]) |
| 45 | [] |
| 46 | >>> heap_sort([-2, -5, -45]) |
| 47 | [-45, -5, -2] |
| 48 | >>> heap_sort([3, 7, 9, 28, 123, -5, 8, -30, -200, 0, 4]) |
| 49 | [-200, -30, -5, 0, 3, 4, 7, 8, 9, 28, 123] |
| 50 | """ |
| 51 | n = len(unsorted) |
| 52 | for i in range(n // 2 - 1, -1, -1): |
| 53 | heapify(unsorted, i, n) |
| 54 | for i in range(n - 1, 0, -1): |
| 55 | unsorted[0], unsorted[i] = unsorted[i], unsorted[0] |
| 56 | heapify(unsorted, 0, i) |
| 57 | return unsorted |
| 58 | |
| 59 | |
| 60 | if __name__ == "__main__": |