Chapter 43 of 65

Heap Sort

On this page

Imagine a cricket selector who has to rank 15 players from best to worst. One way is to keep asking the same simple question: "Who is the best player still left?" Pick that player, put them at the top of the ranking, and ask again with the remaining players.

That idea is exactly Selection Sort, and it is slow because finding the best of the remaining players takes O(n) every single time.

But what if the players were kept in a structure that always tells you the best one instantly, and can be repaired in O(log n) after you remove them? You already know such a structure from the previous chapter: the Max Heap.

Combining "pick the largest again and again" with a heap gives us Heap Sort.

Heap Sort is a comparison-based sorting algorithm that first turns the array into a max heap, and then repeatedly swaps the largest element (the root) to the end of the array and repairs the heap on the remaining elements.

Heap Sort is famous for one combination that no other common sort gives you: a guaranteed O(n log n) worst case and O(1) extra space. In this chapter, we build it step by step, trace it on a real array, and see why it is both loved and avoided.


Quick Recap: What We Need from the Heap Chapter

Heap Sort works directly on the array. It never creates tree nodes. It only uses these facts from the Heap chapter:

For a 0-based array, the node at index i has:

Left child  = 2 * i + 1
Right child = 2 * i + 2
Parent      = (i - 1) / 2

Max heap rule: every parent ≥ its children
               so the largest element is always at index 0

And one operation:

siftDown(i): if arr[i] is smaller than one of its children,
             swap it with the LARGER child and repeat from there.
             Stops when both children are smaller (or there are none).

A sift-down moves down at most one level per step, and a heap has about log₂ n levels, so it costs O(log n).

Heap Sort needs one small extra detail: siftDown must know how many elements still belong to the heap. We pass that as a size parameter, because the end of the array will slowly fill up with sorted elements that the heap must not touch.


The Core Idea: Two Phases

Phase 1: BUILD
    Rearrange the array into a max heap.
    Now the largest element is at index 0.

Phase 2: EXTRACT (repeat n - 1 times)
    Swap arr[0] (the largest) with the last element of the heap.
    The largest is now in its final position at the end.
    Shrink the heap by one.
    siftDown(0) to repair the smaller heap.

During Phase 2, the array is split into two regions:

[  max heap (unsorted)   |   sorted, in final positions  ]
 0                  end-1  end                       n-1

The heap shrinks from the right, the sorted part grows from the right.

This is the same shape as Selection Sort. The only difference is how we find the largest remaining element: Selection Sort scans in O(n), Heap Sort reads arr[0] in O(1) and repairs the heap in O(log n).


Phase 1: Building the Max Heap

Let's sort this array:

index:  0   1   2   3   4   5
arr  = [4, 10,  3,  5,  1,  8]

As a tree:
            4
          /   \
        10     3
       /  \   /
      5    1 8

The smart way to build a heap is bottom-up:

  • Leaves (nodes with no children) are already valid heaps of size 1, so we skip them.

  • In a 0-based array of size n, the last non-leaf node is at index n / 2 - 1.

  • We call siftDown on every node from n / 2 - 1 down to 0.

Here n = 6, so we start at index 6 / 2 - 1 = 2.

i = 2 (value 3): its only child is index 5 (value 8). 8 > 3, so swap.

[4, 10, 8, 5, 1, 3]

            4
          /   \
        10     8
       /  \   /
      5    1 3

i = 1 (value 10): children are 5 and 1. Both are smaller, so nothing changes.

i = 0 (value 4): children are 10 and 8. The larger child is 10, so swap 4 and 10.

[10, 4, 8, 5, 1, 3]

            10
          /    \
         4      8
       /  \    /
      5    1  3

4 keeps sinking. Its new children are 5 and 1. The larger is 5, and 5 > 4, so swap again.

[10, 5, 8, 4, 1, 3]

            10
          /    \
         5      8
       /  \    /
      4    1  3

4 is now a leaf, so it stops. Every parent is larger than its children. Phase 1 is complete and the maximum, 10, is at index 0.


Phase 2: Extracting the Maximum Again and Again

Each round: swap the root with the last heap element, shrink the heap, sift down the new root. The part after | is sorted and never touched again.

Start:        [10, 5, 8, 4, 1, 3]

Round 1: swap 10 and 3        → [3, 5, 8, 4, 1 | 10]
         siftDown: 3 vs 5, 8  → swap with 8
                              → [8, 5, 3, 4, 1 | 10]

Round 2: swap 8 and 1         → [1, 5, 3, 4 | 8, 10]
         siftDown: 1 vs 5, 3  → swap with 5 → [5, 1, 3, 4 | 8, 10]
                   1 vs 4     → swap with 4 → [5, 4, 3, 1 | 8, 10]

Round 3: swap 5 and 1         → [1, 4, 3 | 5, 8, 10]
         siftDown: 1 vs 4, 3  → swap with 4
                              → [4, 1, 3 | 5, 8, 10]

Round 4: swap 4 and 3         → [3, 1 | 4, 5, 8, 10]
         siftDown: 3 vs 1     → no swap

Round 5: swap 3 and 1         → [1 | 3, 4, 5, 8, 10]
         heap of size 1       → done

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

Notice two things:

  • We only need n - 1 rounds. When one element is left, it is automatically the smallest and already in place.

  • In Round 2, after the swap the heap size was 4 (indexes 0 to 3). When 1 sank to index 1, its right child would be index 4, but that slot holds the already sorted 8, so siftDown correctly ignored it. This is why the size parameter matters.


Heap Sort in Java

Here is the complete program. It prints the heap after Phase 1 and the array after every round of Phase 2, so you can match it against the trace above.

import java.util.Arrays;

class Main {

    static void heapSort(int[] arr) {

        int n = arr.length;

        // Phase 1: build a max heap (start at the last non-leaf node)
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }

        System.out.println("Max heap: " + Arrays.toString(arr));

        // Phase 2: move the max to the end, shrink the heap, repair it
        for (int end = n - 1; end > 0; end--) {

            swap(arr, 0, end);        // largest goes to its final place
            siftDown(arr, end, 0);    // heap is now arr[0..end-1]

            System.out.println("Placed " + arr[end] + ": " + Arrays.toString(arr));
        }
    }

    // Push arr[i] down until both children are smaller.
    // Only indexes 0..size-1 belong to the heap.
    static void siftDown(int[] arr, int size, int i) {

        while (true) {

            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < size && arr[left] > arr[largest]) {
                largest = left;
            }
            if (right < size && arr[right] > arr[largest]) {
                largest = right;
            }

            if (largest == i) {
                return;               // heap property holds
            }

            swap(arr, i, largest);
            i = largest;              // keep going down
        }
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {

        int[] arr = {4, 10, 3, 5, 1, 8};

        heapSort(arr);

        System.out.println("Sorted:   " + Arrays.toString(arr));
    }
}

Output:

Max heap: [10, 5, 8, 4, 1, 3]
Placed 10: [8, 5, 3, 4, 1, 10]
Placed 8: [5, 4, 3, 1, 8, 10]
Placed 5: [4, 1, 3, 5, 8, 10]
Placed 4: [3, 1, 4, 5, 8, 10]
Placed 3: [1, 3, 4, 5, 8, 10]
Sorted:   [1, 3, 4, 5, 8, 10]

Understanding the Code

  • Why n / 2 - 1? A node at index i has a left child only if 2i + 1 < n. The largest such i is n / 2 - 1 (integer division). Every index after it is a leaf.

  • Why go from right to left in Phase 1? siftDown assumes both subtrees below i are already heaps. Going backwards guarantees that the children are fixed before their parent.

  • Why siftDown(arr, end, 0)? After the swap, the heap is arr[0..end-1], which has exactly end elements. Passing end as the size keeps the sorted part safe.

  • Why iterative instead of recursive? A loop uses O(1) extra space. A recursive siftDown is also correct but uses O(log n) stack space.


Why Building a Heap Takes Only O(n)

Phase 1 calls siftDown about n / 2 times, and each call is O(log n). So it looks like O(n log n). That bound is correct, but it is not tight. The real cost is O(n), and this is a favourite interview question.

The trick is that a siftDown starting at a node can only travel as far as that node's height (its distance from the bottom), and most nodes are near the bottom:

Height of node   How many nodes (about)   Max swaps each   Total work
      0                 n/2                     0               0
      1                 n/4                     1              n/4
      2                 n/8                     2              2n/8
      3                 n/16                    3              3n/16
     ...                ...                    ...             ...
   log n                 1                    log n           log n

Adding up the last column:

Total = n × (1/4 + 2/8 + 3/16 + 4/32 + ...)
      = n/2 × (1/2 + 2/4 + 3/8 + 4/16 + ...)
      = n/2 × 2
      = n

(The series 1/2 + 2/4 + 3/8 + ... adds up to exactly 2.)

Half the nodes are leaves and do no work at all. Only one node, the root, can travel the full log n levels. So:

Bottom-up build (siftDown from n/2 - 1 to 0)  → O(n)
Building by inserting one element at a time  → O(n log n)

Both give a valid heap, but the bottom-up method is faster, and it is the one Heap Sort uses.

This O(n) build does not make Heap Sort linear, because Phase 2 is still O(n log n). But it matters for problems where you build a heap once and extract only a few elements (see Partial Heap Sort below).


Time Complexity

Phase 1: build heap                 → O(n)
Phase 2: (n - 1) rounds × O(log n)  → O(n log n)

Total                               → O(n log n)

Unlike Quick Sort, Heap Sort has no bad input. The shape of the heap is fixed by n alone, and in Phase 2 the element moved to the root is a value from the bottom of the heap, which usually sinks most of the way down again, whatever the input looks like.

Case

Time

Why

Best

O(n log n)

Even sorted input must be turned into a heap and taken apart again

Average

O(n log n)

Each extraction sifts through about log n levels

Worst

O(n log n)

A sift-down can never go deeper than the heap height

(One special case: if all elements are equal, every siftDown stops immediately and the sort finishes in O(n). For distinct values, the best case is Θ(n log n).)

Seeing It in Numbers

Let's count the comparisons Heap Sort makes on 1,000 numbers that are sorted, reverse sorted, and shuffled. The shuffle uses the same seed as the experiment in the Quick Sort chapter.

import java.util.Random;

class Main {

    static long comparisons;

    static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
        for (int end = n - 1; end > 0; end--) {
            int t = arr[0]; arr[0] = arr[end]; arr[end] = t;
            siftDown(arr, end, 0);
        }
    }

    static void siftDown(int[] arr, int size, int i) {
        while (true) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < size) {
                comparisons++;
                if (arr[left] > arr[largest]) largest = left;
            }
            if (right < size) {
                comparisons++;
                if (arr[right] > arr[largest]) largest = right;
            }
            if (largest == i) return;
            int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
            i = largest;
        }
    }

    static long count(int[] arr) {
        comparisons = 0;
        heapSort(arr);
        return comparisons;
    }

    public static void main(String[] args) {

        int n = 1000;

        int[] sorted = new int[n];
        int[] reversed = new int[n];
        for (int i = 0; i < n; i++) {
            sorted[i] = i;
            reversed[i] = n - 1 - i;
        }

        int[] shuffled = sorted.clone();
        Random rnd = new Random(42);
        for (int i = n - 1; i > 0; i--) {          // Fisher-Yates shuffle
            int j = rnd.nextInt(i + 1);
            int t = shuffled[i]; shuffled[i] = shuffled[j]; shuffled[j] = t;
        }

        System.out.println("Sorted input:   " + count(sorted) + " comparisons");
        System.out.println("Reversed input: " + count(reversed) + " comparisons");
        System.out.println("Shuffled input: " + count(shuffled) + " comparisons");
    }
}

Output:

Sorted input:   17583 comparisons
Reversed input: 15965 comparisons
Shuffled input: 16834 comparisons

All three are in the same range, roughly 1.6 to 1.8 × n log₂ n (and n log₂ n ≈ 9,966 here). Compare this with Quick Sort, which needed 499,500 comparisons on sorted input. Heap Sort simply does not have a worst case to fall into.

But also notice the other side: on the same shuffled array, Quick Sort needed only 11,482 comparisons. On random data, Heap Sort does noticeably more work. Keep this in mind for the comparison section.


Space Complexity

Heap Sort rearranges elements inside the original array. With the iterative siftDown above, it only needs a few variables:

Extra space → O(1)
In-place    → Yes

Compare this with Merge Sort (O(n) temporary array) and Quick Sort (O(log n) stack on average, O(n) in the worst case). Heap Sort is the only one of the three that is O(n log n) in time and O(1) in space at the same time.

If you write siftDown recursively, the call stack grows to the heap height, so the extra space becomes O(log n). Interviewers sometimes ask about exactly this detail.


Heap Sort Is Not Stable

A stable sort keeps equal elements in their original order (see the Sorting Algorithms chapter). Heap Sort does not, because the swap between the root and the last element jumps across the whole array.

Take three records sorted by number, where 2a and 2b are equal keys and 2a comes first:

Start:            [2a, 2b, 1]
Build heap:       2a is already ≥ both children → [2a, 2b, 1]

Round 1: swap root and last → [1, 2b | 2a]
         siftDown: 2b > 1   → [2b, 1 | 2a]

Round 2: swap root and last → [1 | 2b, 2a]

Result:           [1, 2b, 2a]   ← 2b is now before 2a

The two equal keys swapped their order. If you need stability (for example, sorting students by marks while keeping the alphabetical order for equal marks), use Merge Sort instead.


Heap Sort Is Not Adaptive

An adaptive sort runs faster when the input is already partly sorted. Insertion Sort is the classic example: O(n) on sorted input.

Heap Sort is not adaptive. As the experiment above showed, a sorted array costs about the same as a random one. In fact, building a max heap from an ascending array is extra work: every non-leaf node is smaller than its children, so every one of them has to sift down.


Sorting in Descending Order

A max heap sends the largest element to the end each round, which produces ascending order. For descending order, use a min heap instead: flip the two comparisons in siftDown.

// Min-heap version of siftDown → heapSort produces descending order
if (left < size && arr[left] < arr[smallest]) {
    smallest = left;
}
if (right < size && arr[right] < arr[smallest]) {
    smallest = right;
}

Now the smallest element is moved to the end each round, so the array ends up largest first.

A common mistake is to think "ascending needs a min heap". With the in-place method it is the opposite: max heap → ascending, min heap → descending.


Partial Heap Sort: The Top K Elements

Sometimes you don't need the whole array sorted. You only need the k largest values, for example the top 3 marks in a class.

Heap Sort can simply stop early: build the heap once, then do only k rounds of Phase 2.

class Main {

    // Prints the k largest values, largest first, using only k extractions
    static void printKLargest(int[] arr, int k) {

        int n = arr.length;

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

        for (int count = 0; count < k; count++) { // k extractions: O(k log n)
            int end = n - 1 - count;
            System.out.print(arr[0] + " ");
            swap(arr, 0, end);
            siftDown(arr, end, 0);
        }
        System.out.println();
    }

    static void siftDown(int[] arr, int size, int i) {
        while (true) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < size && arr[left] > arr[largest]) largest = left;
            if (right < size && arr[right] > arr[largest]) largest = right;
            if (largest == i) return;
            swap(arr, i, largest);
            i = largest;
        }
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {

        int[] marks = {67, 92, 45, 88, 73, 99, 51, 80};

        System.out.print("Top 3 marks: ");
        printKLargest(marks, 3);
    }
}

Output:

Top 3 marks: 99 92 88

The cost is:

Build heap      → O(n)
k extractions   → O(k log n)
Total           → O(n + k log n)

For small k, this is much better than sorting everything in O(n log n). This is where the O(n) build really pays off. In the next chapter, you'll see another popular way to solve Top K problems using Java's PriorityQueue with a heap of size k.


Heap Sort vs Merge Sort vs Quick Sort

Property

Heap Sort

Merge Sort

Quick Sort

Best time

O(n log n)

O(n log n)

O(n log n)

Average time

O(n log n)

O(n log n)

O(n log n)

Worst time

O(n log n)

O(n log n)

O(n²)

Extra space

O(1)

O(n)

O(log n) stack (average)

In-place

Yes

No (for arrays)

Yes

Stable

No

Yes

No

Adaptive

No

No (basic version)

No

Cache behaviour

Poor (jumps from i to 2i + 1)

Good (sequential scans)

Very good (sequential scans)

Practical speed on random data

Usually the slowest of the three

Good

Usually the fastest

Why Is Heap Sort Slower in Practice?

Its Big O is as good as the others, but:

  • Poor cache use. siftDown jumps from index i to 2i + 1. For a large array, these positions are far apart in memory, so the CPU cache helps much less than with the sequential scans of Quick Sort and Merge Sort.

  • More comparisons. As we measured, it did about 16,800 comparisons where Quick Sort did about 11,500 on the same shuffled data.

Where Heap Sort Is Actually Used

Heap Sort's real job in practice is to be a safety net. Introsort (introspective sort) starts with Quick Sort, watches the recursion depth, and switches to Heap Sort if the depth grows too large (a sign of bad pivots). That way it gets Quick Sort's speed on normal data and Heap Sort's O(n log n) guarantee in the worst case. The std::sort function in common C++ standard library implementations is built this way.

Heap Sort is also a good choice in memory-constrained systems (like embedded devices) where you cannot afford extra memory and cannot risk an O(n²) worst case.


Common Mistakes

1. Starting the build from the wrong index

For a 0-based array, start at n / 2 - 1 and go down to 0. Starting at n / 2 is harmless (that node is a leaf, so it just wastes a call), but starting at 0 and going upward is wrong: siftDown would run on a parent before its subtrees are heaps.

2. Forgetting to shrink the heap

In Phase 2, siftDown must use the current heap size (end), not n. Using n pulls the already sorted maximums back into the heap and the result is wrong.

3. Comparing with only one child

You must compare with both children and swap with the larger one. Swapping with the left child just because it is bigger than the parent can put a smaller value above a larger right child, breaking the heap.

4. Missing the bounds check

Always check left < size and right < size before reading the children. A node can have no children, or only a left child.

5. Using a min heap for ascending order

For in-place Heap Sort, the root goes to the end of the array. A max heap therefore produces ascending order. A min heap produces descending order.

6. Using 1-based formulas on a 0-based array

Some textbooks store the heap from index 1, where the children are 2i and 2i + 1 and the parent is i / 2. Mixing these with a Java array that starts at index 0 silently breaks the heap.


Interview Tips and Practice

  • Be able to write siftDown and heapSort from memory, and trace them on a 5 or 6 element array.

  • Know the answer to "Why is building a heap O(n)?": most nodes are near the bottom and can only sift down a short distance.

  • Know the trade-off question: "Heap Sort has a better worst case than Quick Sort and less memory than Merge Sort, so why isn't it the default?" Answer: poor cache behaviour, more comparisons, not stable.

  • Mention Introsort when asked how real libraries avoid Quick Sort's worst case.

  • For "k largest" questions, mention both options: build heap plus k extractions (O(n + k log n)), or a size-k min heap (O(n log k)), covered in the next chapter.

Practice problems:

  • Sort an Array (LeetCode 912): Heap Sort passes because it has no O(n²) worst case

  • Kth Largest Element in an Array (LeetCode 215): build a heap, extract k times

  • Last Stone Weight (LeetCode 1046): repeated "take the largest" operations

  • Check if an array represents a max heap (GeeksforGeeks): verify arr[i] ≥ arr[2i+1] and arr[i] ≥ arr[2i+2]

  • Convert a min heap to a max heap (GeeksforGeeks): just run the bottom-up build


The Main Idea

Heap Sort turns the array into a max heap and then repeatedly moves the largest element to the end.

Build a max heap (siftDown from n/2 - 1 down to 0)   → O(n)
     ↓
Swap root (max) with the last heap element
     ↓
Shrink the heap by one
     ↓
siftDown(0) to repair it                              → O(log n)
     ↓
Repeat n - 1 times                                    → O(n log n)

Its key facts:

Best / Average / Worst → O(n log n)
Extra space            → O(1)  (iterative siftDown)
In-place               → Yes
Stable                 → No
Adaptive               → No

Heap Sort is Selection Sort with a heap: instead of scanning for the maximum in O(n), it reads it from the root in O(1) and repairs the heap in O(log n). The result is a guaranteed O(n log n) sort that needs no extra memory.

The heap you used here to sort an array is the same structure behind Java's PriorityQueue. In the next chapter, we'll use it as a Priority Queue to solve scheduling, Top K and graph problems.