Card 03/ 09
Build a Heap Bottom-Up in Linear Time
Sift down every parent from the last one back to the root.
A min-heap can be built from n unordered items in O(n) time by treating the array as a tree and sifting down every parent, starting from the last parent and working back to the root. This card covers that bottom-up build, traced on seven items, and why its cost grows linearly rather than as n log n.
A min-heap is a complete binary tree, stored level by level in an array, in which every parent is no larger than its children. Sift-down repairs one item that may be larger than its children: it swaps the item with its smaller child, again and again, until no child is smaller. It works only when the subtrees below the item are already heaps.
That condition sets the order of the build. Every leaf, a node with no children, is already a heap of one item, so only the parents need work. In an array of n items the last parent is at index n // 2 - 1, where // divides and rounds down. Sifting down each parent from there back to index 0 means that whenever a parent sinks, both subtrees below it have already been fixed. The array to build from is 9 4 7 1 8 2 6, which has seven items, so the last parent is at index 2.
9, index 0, sifted last
4, index 1, sifted second
1, index 3, a leaf
8, index 4, a leaf
7, index 2, the last parent, sifted first
2, index 5, a leaf
6, index 6, a leaf
Building a heap from 9 4 7 1 8 2 6, one parent at a time
Sift down 7 at index 2
The children of index 2 hold 2 and 6. The smaller is 2, at index 5, and 7 is larger than it, so they swap. 7 is now a leaf and stops. The array is 9 4 2 1 8 7 6.
Sift down 4 at index 1
The children of index 1 hold 1 and 8. The smaller is 1, at index 3, and 4 is larger, so they swap. 4 is now a leaf. The array is 9 1 2 4 8 7 6, and both subtrees of the root are heaps.
Sift down 9 at the root
The children of index 0 hold 1 and 2. 9 swaps with the smaller, 1, giving 1 9 2 4 8 7 6. At index 1, the children of 9 hold 4 and 8, so 9 swaps with 4, giving 1 4 2 9 8 7 6. At index 3, 9 is a leaf, and the sift stops. The root's sift took two swaps because it could sink the full height of the tree.
The finished heap
The build made four swaps in all, and the array 1 4 2 9 8 7 6 is a min-heap. A run of the trace printed the same four swaps, and Python's heapq.heapify, which builds a heap in place in a list, left the same array.
1, index 0
4, index 1
9, index 3, sank from the root
8, index 4
2, index 2
7, index 5
6, index 6
The build is linear because most items have little room to fall. About half of the items are leaves and never move. About a quarter sit one level above the leaves and can sink at most one level, an eighth can sink at most two, and only the root can sink the whole height. Adding these limits up gives at most about n swaps, however large n grows. A run on 1,023 items in descending order, where every parent has to sink as far as it can, counted 1,013 swaps.
An O(n log n) estimate, n sift-downs at O(log n) each, is a true upper bound but not a tight one, because it charges every item for the root's journey. Python's heapq.heapify and Java's PriorityQueue constructor that takes a collection both build this way.
← → move through sections and cards