Build the Starting Max-Heap From the Bottom Up

Sift down every parent, from the last one to the root, and the array becomes a heap in O(n).

Heapsort's first phase turns an unsorted array into a max-heap in place, by sifting down every parent from the last one back to the root. This card walks through the method, a prediction to make, and a trace of the build on six numbers.

In the array layout a heap uses, the children of index i are at 2i + 1 and 2i + 2. To sift down an item, compare it with the larger of its children; if that child is larger, swap them and repeat from the child's index, and stop when the item is at least as large as both children or has none. The build has three moves:

Find the last parent. In an array of n items it is at index ⌊n/2⌋ − 1, and every item after it is a leaf, already a heap of one item.
Sift down the item at that index, within the whole array.
Step back one index and repeat, down to index 0, the root.

Working backwards is what makes it correct. When a parent is sifted down, the parts of the tree under its children are already heaps, because their roots come later in the array and were handled first, so one sift-down makes the part under the parent a heap too.

Build a max-heap from 4 7 2 9 5 8. Before the trace, predict the array once the build has finished.

Show the prediction

The array is 9 7 8 4 5 2. 9 rises to the root, and 4, which started there, sinks two levels to index 3. The array is a heap, not a sorted list: 7 sits before 8, and 4 before 5, because a heap only orders each parent against its own children.

In the trace, i marks the parent being sifted down, and each frame shows the array once that sift-down has finished.

Building a max-heap from 4 7 2 9 5 8, one sift-down per parent

Input4 7 2 9 5 8

Start
1. 4
2. 7
3. 2i
4. 9
5. 5
6. 8
Six items, so the last parent is at index 6/2 − 1 = 2, holding 2. The items at indices 3, 4 and 5 are leaves, each already a heap of one item.
Sift 2
1. 4
2. 7
3. 8i
4. 9
5. 5
6. 2
2 has one child, 8 at index 5. 8 is larger, so they swap, and the part of the tree under index 2 is a heap.
Sift 7
1. 4
2. 9i
3. 8
4. 7
5. 5
6. 2
7 has children 9 and 5. 9 is the larger and beats 7, so they swap, and 7 lands at index 3, a leaf.
Sift 4
1. 9i
2. 7
3. 8
4. 4
5. 5
6. 2
4 has children 9 and 8. It swaps with 9, then with 7, the larger of its new children 7 and 5, and comes to rest at index 3. The array is a max-heap.

Result9 7 8 4 5 2

The run's last frame matches the prediction. The three sift-downs made 1, 1 and 2 swaps: the parents near the bottom have little room to fall, and only the root could fall two levels.

That imbalance is why the build costs O(n) and not O(n log n). About half the items are leaves and never move, a quarter can fall one level, an eighth two levels, and only the root can fall the full height of the tree, so the total work adds up to a constant times n. Building a heap with n separate pushes, each sifting up, is the slower way, O(n log n) in the worst case. A run building the heap for 1,000 shuffled numbers made 1,864 comparisons, where n log₂ n would be nearly 10,000.

The build is the cheap phase. The n − 1 extractions that follow each sift a new root down from the top of the heap, which is where heapsort's O(n log n) comes from.

← → move through sections and cards