Heap Sort

What is heap sort?

Heap sort hides a tree inside the list. It first rearranges the values into a max-heap, a tree where every parent is at least as big as its children. That puts the biggest value at the top. It swaps the top to the end of the list, repairs the heap, and repeats. Each round moves the next biggest value into place.

It is like selection sort with a much faster way to find the biggest value. And unlike most fast sorts, it needs no extra memory and is never slow: O(n log n) every time.

The tree inside the array

There is no separate tree. The position of each value tells you where it sits in the tree:

• The root is a[0].
• The children of a[i] are a[2i + 1] and a[2i + 2].
• The parent of a[i] is a[(i − 1) // 2].

So a[0] has children a[1] and a[2], and a[1] has children a[3] and a[4]. The tree fills row by row, so it is never more than about log₂ n levels tall.

How it works, step by step

Press play above. Blue bars are a parent and child being compared, orange bars are being swapped. The green part at the end grows by one each round.

1. Build the heap. For each parent, from the last one back to a[0], sift it down: compare it with its bigger child, and swap if the child is bigger. Keep going down until it is bigger than both children or has none.
2. Now a[0] is the biggest value. Swap it with the last value in the heap. It is in its final place.
3. The heap is one smaller. The new top is probably too small, so sift it down to repair the heap.
4. Repeat steps 2 and 3 until the heap has one value left.

In the code, sift(i, m) is the repair step, where m is the heap’s current size. The first loop builds the heap, and the second loop swaps the top away and sifts, over and over.

Time and space complexity

Each sift walks down at most one path of the tree, which is about log n levels. The second phase does n − 1 sifts, so it costs O(n log n). Building the heap first costs only O(n), because most values sit near the bottom of the tree and barely move.

Best, average and worst case are all O(n log n). The order of the input doesn’t change the shape of the tree, so no input makes heap sort slow. Try the “reversed” and “nearly sorted” presets: the counts barely change.

Space is O(1). The heap lives inside the list itself, and the sift loop needs no recursion.

Common mistakes

• Comparing with the left child only. You must swap with the bigger of the two children, or the heap breaks.
• Sifting past the heap. After the swap, the sorted tail is no longer part of the heap, so sift must stop at size m, not n.
• Building the heap from the top down with sifts. Start from the last parent, n // 2 − 1, and work back to 0.
• Expecting stability. The long-distance swaps reorder equal values, so heap sort is not stable.

When to use it

Use heap sort when you need a guaranteed O(n log n) and can’t spare extra memory. That is why introsort, the sort behind many C++ standard libraries, falls back to heap sort if quicksort starts going badly.

In practice, quicksort and merge sort are usually faster, because heap sort jumps around memory and makes poor use of the CPU cache. The heap itself is very useful on its own: it is how priority queues work, like Python’s heapq.

Questions

Is heap sort stable?

No. Swapping the top of the heap to the end can reorder equal values.

Why is building a heap O(n) and not O(n log n)?

Half the values are leaves and don’t move at all, a quarter move at most one level, and so on. Added up, that is less than 2n steps.

Is heap sort faster than quicksort?

Not usually. Quicksort is often faster on average, but heap sort is never worse than O(n log n) and needs no extra space.