Heap sort visualization

Heap sort is a comparison-based sorting algorithm that first arranges the array as a max-heap, then repeatedly swaps the largest value, the root, to the end and repairs the heap. It sorts in place and always runs in O(n log n) time.

A max-heap is stored in the array itself: the children of index i are at 2i + 1 and 2i + 2, and every value is at least as large as its children. So index 0 always holds the largest value.

How it works

1. Build the heap. Indexes from n / 2 up are leaves, so they are already heaps. Go from the last parent back to index 0 and sift down each value: swap it with its larger child until it is at least as large as both.
2. Take the largest out. Swap the root with the last value of the heap. That index is now final, so the heap is one place shorter.
3. Sift the new root down to repair the heap, and repeat step 2 until the heap has one value left.

Time and space complexity

A sift down walks at most the height of the heap, about log n levels. The second phase does it n - 1 times, so it costs O(n log n) however the values are ordered. Building the heap costs only O(n).

• Best, average and worst: O(n log n), because the second phase never depends on the order of the input.
• Space: O(1), because everything happens inside the array: it is in place.

A worked example

Sort 5, 3, 8, 1, 9, 2, 7. Phase 1 builds the max-heap: index 2 (the 8) already beats its children, index 1 swaps the 3 with its larger child 9, and index 0 swaps the 5 with the 9 and then stays at index 1, because its children 1 and 3 are smaller. Then phase 2 runs 6 rounds. Each round swaps the root into its final place and sifts the new root down inside the shorter heap. The table shows the heap and the finished part after each round.

The last value left in the heap, 1, is already in place, so the array reads 1, 2, 3, 5, 7, 8, 9. The whole run makes 19 comparisons and 24 writes, where a swap counts as two writes. Phase 1 used 8 of those comparisons and 2 swaps. The array was sorted without any extra array, since the heap and the finished part share the same 7 slots.

Pseudocode

The code counts indexes from 0, so the children of i are 2i + 1 and 2i + 2. SIFT-DOWN is the textbook's MAX-HEAPIFY, and the first loop is BUILD-MAX-HEAP. The parameter size is the length of the heap.

HEAP-SORT(A)
    n = A.length
    for i = floor(n / 2) - 1 downto 0
        SIFT-DOWN(A, i, n)
    for end = n - 1 downto 1
        swap A[0] and A[end]
        SIFT-DOWN(A, 0, end)

SIFT-DOWN(A, i, size)
    while true
        l = 2i + 1
        r = 2i + 2
        largest = i
        if l < size and A[l] > A[largest]
            largest = l
        if r < size and A[r] > A[largest]
            largest = r
        if largest == i
            return
        swap A[i] and A[largest]
        i = largest

The second loop passes end as the size, so the heap shrinks by one each round and never touches the values that are already final. That is the fix for the mistake in the box below.

Stability

Heap sort is not stable. Sorting [2a, 2b, 1] gives [1, 2b, 2a]: the two equal values changed places.

When to use it, and when not to

• Use it when you need a guaranteed O(n log n) time and little extra memory. Merge sort has the guarantee but needs O(n) space; quick sort is in place but can degrade to O(n²).
• Avoid it when you need a stable sort, or when speed on typical data matters most: quick sort is usually faster in practice.

Where it is used

• The fallback in introsort. Introsort starts as quick sort and switches to heap sort when the recursion goes deeper than a fixed limit, which caps the worst case at O(n log n). It is the design behind std::sort in GNU's libstdc++, among other C++ standard libraries.
• Kernels with little stack. The Linux kernel's sort() is a heap sort. Its source gives the reasons: it is non-recursive, so it needs no deep stack, and it avoids the O(n²) worst case of quick sort without extra code.
• Partial sorting. To get only the k smallest or largest values, build the heap in O(n) and run the second phase for k rounds. That costs O(n + k log n), far less than a full sort when k is small.

Variations and related ideas

Heap sort is selection sort with a heap to find the largest remaining value in O(log n) instead of scanning for it, which turns O(n²) into O(n log n). The heap itself is the subject of the binary heap lesson, which uses a min-heap. To compare it with other sorts on the same inputs, see merge sort vs heap sort (same time guarantee, but merge sort is stable and needs O(n) extra space), quick sort vs heap sort and selection sort vs heap sort. Smoothsort is a variant that runs faster on nearly sorted input.