Implement Heap Sort. Build a max-heap from the array, then repeatedly extract the maximum element and place it at the end of the array.
Input: [12, 11, 13, 5, 6, 7] → Output: [5, 6, 7, 11, 12, 13]Input: [4, 10, 3, 5, 1] → Output: [1, 3, 4, 5, 10]
Phase 1: Build max-heap by calling heapify on all non-leaf nodes bottom-up. Phase 2: Repeatedly swap root (max) with last unsorted element, reduce heap size, and heapify root.
- Build max-heap: for i from n/2-1 down to 0, call heapify(arr, n, i).
- Heapify: find largest among node i and its children, swap if needed, recurse down.
- Extract phase: for i from n-1 to 1, swap arr[0] with arr[i], call heapify(arr, i, 0).
class HeapSort {
public void sort(int[] arr) {
int n = arr.length;
// Build max-heap
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
// Extract elements
for (int i = n - 1; i > 0; i--) {
int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
heapify(arr, i, 0);
}
}
private void heapify(int[] arr, int n, int i) {
int largest = i, left = 2*i+1, right = 2*i+2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
heapify(arr, n, largest);
}
}
}
- Time Complexity: O(N log N) all cases
- Space Complexity: O(1) in-place, O(log N) for recursion stack