Heap Sort builds a max-heap from the input array, then repeatedly extracts the maximum element and places it at the end. It combines the O(n log n) guarantee of Merge Sort with the O(1) space of in-place sorting. While not stable, it is optimal in both time and space for comparison sorting.
void heapify(vector<int>& arr, int n, int i) {
int largest = i, l = 2*i+1, r = 2*i+2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
void heapSort(vector<int>& arr) {
int n = arr.size();
for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
for (int i = n-1; i > 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); }
}A max-heap is a complete binary tree where every node is greater than or equal to its children. Stored in an array, the children of node i are at 2i+1 and 2i+2. This property lets us find the maximum in O(1).
We build a max-heap from the array in O(n) time by calling heapify on all non-leaf nodes from bottom to top. This is more efficient than inserting elements one by one which would take O(n log n).
We repeatedly swap the root (maximum element) with the last element of the heap, reduce heap size by one, and restore the heap property by calling heapify on the root. Each extraction is O(log n).
Heap Sort is optimal: O(n log n) worst case with O(1) extra space. It is not cache-friendly (poor locality) which is why Quick Sort is faster in practice despite similar asymptotic complexity.
Heap Sort uses which data structure?
What is the time complexity of building a heap (heapify)?
Heap Sort is: