Heap Sort

Share

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.

Example 1
Input: [12, 11, 13, 5, 6, 7] → Output: [5, 6, 7, 11, 12, 13]
Example 2
Input: [4, 10, 3, 5, 1] → Output: [1, 3, 4, 5, 10]

Solution Approach

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).
Java
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