Max-Heap Sort
Is a in-place sorting algorithm taking advantage of the properties of a max-heap.
def heap_sort(arr):
build_max_heap(arr)
for i in reversed(range(1, len(arr))):
swap(arr, 0, i)
arr.length -= 1
max_heapify(arr, 0)Code Snippet 1:
Heap sort implementation. alg:heap_sort
Heap sort can be seen in alg:heap_sort.
Heap-sort [see page 17, works] by constructing a heap from the collection, swapping the first
value of the heap (the largest value in the array by the max-heap property) and
the end of the array, then shrinking the perceived size of the array by one and
re-establishing the max-heap property by calling build_max_heap on the root.
This has a runtime complexity of \( \mathcal{O}(n \log n) \).