Heap Sort

Heap sort combines the best of both worlds: guaranteed O(n log n) time like merge sort, and in-place sorting like quicksort. It uses a max-heap to repeatedly pull out the largest element and build the sorted array from right to left.

The algorithm has two distinct phases:

1. Build a max-heap from the unsorted array → O(n).
2. Extract the maximum repeatedly, placing each at the end → O(n log n).

Step 1: Build the Max-Heap — O(n)

A max-heap stored in an array follows these index relationships:

• Parent of node at index i: (i - 1) / 2
• Left child of node at index i: 2 * i + 1
• Right child of node at index i: 2 * i + 2

The siftDown operation restores the heap property for a node by swapping it downward with its largest child until the property holds:

void siftDown(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int 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 temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        siftDown(arr, n, largest);  // Continue sifting down
    }
}

To build the heap, start from the last non-leaf node and sift down every node up to the root:

void buildMaxHeap(int[] arr) {
    int n = arr.length;
    // Last non-leaf node is at index n/2 - 1
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }
}

Why O(n) and Not O(n log n)?

The intuitive estimate says: n/2 nodes × O(log n) sift-down each = O(n log n). But this overestimates dramatically because most nodes are near the bottom and have small heights.

The precise analysis counts actual work per level:

Level (from bottom)	Nodes at this level	Sift-down cost
0 (leaves)	~n/2	0 (skipped)
1	~n/4	1 swap
2	~n/8	2 swaps
h	~n/2^(h+1)	h swaps

Total work:

$$\sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot h = \frac{n}{2} \sum_{h=0}^{\log n} \frac{h}{2^h}$$

The series $\sum_{h=0}^{\infty} h/2^h$ converges to 2. So total work = n/2 × 2 = O(n).

The key insight: the vast majority of nodes sit at the bottom levels where sifting is cheap. Only one node (the root) requires a full O(log n) sift-down.

Step 2: Sort — O(n log n)

Once the max-heap is built, the maximum element sits at index 0. The extraction loop repeatedly:

1. Swaps the root (maximum) with the last unsorted element.
2. Shrinks the heap size by 1 (the swapped element is now in its final position).
3. Sifts down the new root to restore the heap property.

void extractionLoop(int[] arr) {
    int n = arr.length;
    for (int i = n - 1; i > 0; i--) {
        // Swap max (root) with last unsorted element
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Restore heap property for reduced heap
        siftDown(arr, i, 0);    // heap size is now i
    }
}

Each extraction takes O(log n) for the sift-down, and we perform n - 1 extractions, giving O(n log n) for this phase.

Complete Heap Sort

Putting both phases together:

void heapSort(int[] arr) {
    int n = arr.length;
    if (n <= 1) return;

    // Phase 1: Build max-heap — O(n)
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }

    // Phase 2: Extract max repeatedly — O(n log n)
    for (int i = n - 1; i > 0; i--) {
        // Move current max to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Sift down root in reduced heap
        siftDown(arr, i, 0);
    }
}

Visual Walkthrough

Starting array: [4, 10, 3, 5, 1]

Build Max-Heap (process nodes from index 1 down to 0):

Index 1 (value 10): children are 5,1 → 10 > both → no swap
Index 0 (value 4):  children are 10,3 → swap 4↔10
                    Now 4 at index 1: children are 5,1 → swap 4↔5
Heap: [10, 5, 3, 4, 1]

Extraction Phase:

Step 1: Swap 10↔1 → [1, 5, 3, 4, | 10]
        Sift 1 down → [5, 4, 3, 1, | 10]

Step 2: Swap 5↔1 → [1, 4, 3, | 5, 10]
        Sift 1 down → [4, 1, 3, | 5, 10]

Step 3: Swap 4↔3 → [3, 1, | 4, 5, 10]
        Sift 3 down → [3, 1, | 4, 5, 10]

Step 4: Swap 3↔1 → [1, | 3, 4, 5, 10]

Result: [1, 3, 4, 5, 10] ✓

The | marks the boundary between the unsorted heap portion and the sorted tail.

Analysis

Time Complexity

• Build heap: O(n) — as proven by the geometric series argument.
• Extraction phase: n - 1 extractions × O(log n) sift-down = O(n log n).
• Total: O(n) + O(n log n) = O(n log n) for ALL cases.

There is no best-case optimization. Even if the array is already sorted, heap sort still builds the heap and performs all extractions. It always does O(n log n) work.

Space Complexity

O(1) auxiliary space. Heap sort is truly in-place — it rearranges elements within the input array. The only extra memory is a few variables for swapping and indices.

If siftDown is implemented recursively, the call stack uses O(log n) space. An iterative siftDown eliminates even that:

void siftDownIterative(int[] arr, int n, int i) {
    while (true) {
        int largest = i;
        int left = 2 * i + 1;
        int 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) break;

        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        i = largest;
    }
}

Stability

Heap sort is NOT stable. The heap operations destroy the relative order of equal elements. When the root is swapped with the last element, an equal element can leapfrog over others with the same value.

Adaptivity

Heap sort is NOT adaptive. It performs the same number of operations regardless of the input’s initial order. A nearly sorted array gets no benefit.

Comparison: Heap Sort vs. Merge Sort vs. Quicksort

Property	Heap Sort	Merge Sort	Quicksort
Best case	O(n log n)	O(n log n)	O(n log n)
Average case	O(n log n)	O(n log n)	O(n log n)
Worst case	O(n log n)	O(n log n)	O(n²)
Space	O(1)	O(n)	O(log n)
Stable	No	Yes	No
In-place	Yes	No	Yes
Cache performance	Poor	Moderate	Excellent
Adaptive	No	No (TimSort is)	Somewhat

Heap sort’s Achilles’ heel is cache performance. The sift-down operation jumps between parent and child indices (i → 2i+1 → 4i+3 → …), causing cache misses because these positions are far apart in memory. Quicksort’s partitioning scans elements sequentially, keeping data in cache lines.

This cache disadvantage explains why heap sort, despite its theoretical guarantees, is typically 2–3× slower than quicksort in practice on modern hardware.

When to Use Heap Sort

Heap sort occupies a specific niche: guaranteed O(n log n) worst-case with O(1) extra space. This combination is unique among comparison sorts.

Use heap sort when:

• Real-time systems require hard time guarantees (quicksort’s O(n²) worst case is unacceptable).
• Memory is severely constrained (merge sort’s O(n) extra space is too expensive).
• Partial sorting is the goal (see below).

Partial Sorting: Finding K Largest Elements

Heap sort excels at finding the K largest (or smallest) elements. Build the max-heap in O(n), then extract K times:

int[] kLargest(int[] arr, int k) {
    int n = arr.length;

    // Build max-heap — O(n)
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }

    // Extract K times — O(K log n)
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = arr[0];
        arr[0] = arr[n - 1 - i];
        siftDown(arr, n - 1 - i, 0);
    }
    return result;
}

Total time: O(n + K log n). When K is small relative to n, this beats sorting the entire array. For K = 1, this reduces to finding the maximum after heap construction: O(n) total.

For finding the K-th largest element specifically, quickselect (O(n) average) is usually a better choice. But when you need all K largest elements in sorted order and want a worst-case guarantee, the heap approach delivers.

Interviewer Tips

• Know the two phases: Build heap (O(n)) + extract max (O(n log n)). Interviewers test whether you understand both and can articulate why build-heap is linear.
• In-place advantage: when an interviewer asks “sort with guaranteed O(n log n) and O(1) space,” heap sort is the only comparison sort that satisfies both constraints.
• Priority queue connection: heap sort is essentially “insert everything into a priority queue, then extract everything.” If you know how priority queues work, you know heap sort.
• Don’t reach for heap sort first: in general sorting problems, quicksort or merge sort are better defaults. Mention heap sort when the constraints specifically demand worst-case guarantees with no extra space.
• Partial sorting variant: the “find K largest elements” pattern is a common heap interview question. Lead with the O(n + K log n) approach using heap sort’s extraction phase.