Heap Sort

Last updated Nov 8, 2022 Edit Source

Data structure based sorting algorithm using Heaps.

Makes use of the Partial Order Tree property: A tree is a maximising partial order tree if and only if each node has a key value greater than or equal to each of its child nodes.

1. Create a maximizing heap
2. Remove the root node, giving us the largest value. Fill an array from the back with this max value
3. Fix the heap structure
4. Repeat until we obtain a sorted array

Remove the max element and retain the heap structure using

Summary of complexities for Heapsort and corresponding heap structure methods:

Heapsort has a best, worst and average case time complexity of $O(nlogn)$