Build Heap (Heapify) Visualizer — Why It's O(n)

What is build-heap (heapify)?

Build-heap — also called heapify — turns an arbitrary array into a binary heap in place by sifting down every internal node, starting with the last one at index ⌊n/2⌋ − 1 and working back to the root. A single sift-down can cost O(log n), but most nodes sit near the bottom of the tree and barely move, so the total is O(n) — fewer than n swaps — compared with O(n log n) for inserting the keys one at a time.

How it works

Read the array as a complete binary tree: a[0] is the root and the children of i are 2i + 1 and 2i + 2.
Skip the leaves. Indices ⌊n/2⌋ to n − 1 have no children, so each is already a one-node heap.
For i from ⌊n/2⌋ − 1 down to 0, sift down a[i]: swap it with its larger child (in a max-heap) until it is ≥ both children or becomes a leaf.
When the loop finishes at the root, every subtree — and therefore the whole array — satisfies the heap property.

Why bottom-up works

Sift-down has one precondition: both subtrees below i must already be heaps, so the only key that can be out of place is a[i] itself. Processing indices from the back towards the front guarantees that. The children of i sit at larger indices, so by the time the loop reaches i their subtrees have already been fixed. Each step merges two valid heaps and one new key into a bigger valid heap, and the final step at index 0 produces the whole heap.

Going the other way — sifting down from the root first — does not work. When the root is processed its subtrees are still unordered, so a large key buried deep in the tree never gets a chance to rise.

Why it is O(n), not O(n log n)

The naive bound multiplies n/2 sift-downs by O(log n) each. That badly overestimates, because a sift-down costs the height of its node, not the height of the tree, and most nodes are short.

In a complete tree of n nodes about n/2 nodes are leaves (height 0, no work), n/4 have height 1 (at most one swap), n/8 have height 2, and so on — at most ⌈n / 2^(h+1)⌉ nodes of height h. So the total number of swaps is at most

Σ over h of (n / 2^(h+1)) · h = n · (1/4 + 2/8 + 3/16 + 4/32 + …) = n · 1 = n.

The exact figure is even neater: the heights of all nodes in a complete binary tree with n nodes add up to n minus the number of 1-bits in n. With at most two comparisons per level, build-heap makes fewer than n swaps and fewer than 2n comparisons. The visualizer prints each level's height in the left margin and reports this bound at the end of every build.

Worked example: 12, 5, 30, 8, 42, 17, 3, 25, 9, 36

This array is preloaded above. n = 10, so the leaves are indices 5–9 and the loop runs i = 4, 3, 2, 1, 0:

i = 4 (42): its only child is 36, which is smaller — nothing to do.
i = 3 (8): children 25 and 9; 8 sinks below 25. One swap.
i = 2 (30): children 17 and 3; already a heap.
i = 1 (5): children 25 and 42; 5 swaps with 42, then with 36 below it. Two swaps.
i = 0 (12): children 42 and 30; 12 swaps with 42, then with 36, and stops above 5. Two swaps.

The result is the max-heap [42, 36, 30, 25, 12, 17, 3, 8, 9, 5] after 5 swaps — under the bound of 8 (the sum of all node heights, 10 minus the two 1-bits of 10) and under n = 10. The loop never even visited the five leaves.

Bottom-up build vs inserting one at a time

You can also build a heap by starting empty and inserting each key with sift-up. It is correct, but the costs are reversed: sift-up costs a node's depth, and most nodes are deep. In the worst case — ascending keys into a max-heap — every new key is the new maximum and climbs all the way to the root, Θ(n log n) in total. For 1,023 ascending keys that is 8,194 swaps by insertion versus 1,013 with bottom-up build-heap.

Insertion still has its place: it works online, when keys arrive one at a time, and on random input its average cost is O(n) as well. But when you have the whole array up front, the bottom-up build is the right tool — it is what Python's heapq.heapify, C++'s std::make_heap and Java's PriorityQueue(Collection) constructor use.

Where build-heap is used

Heap sort, phase 1: turning the input into a max-heap is the O(n) first half of the algorithm.
Priority queues from a batch: load all known jobs or edges at once instead of making n pushes.
Top-k selection: heapify n items, then pop k times — O(n + k log n).
Merging k sorted lists: heapify the k list heads, then repeatedly pop the smallest and push its successor.

Common mistakes

Looping upwards (i from 0 to n/2 − 1) with sift-down — the subtrees are not heaps yet, so the result is not a heap.
Starting at n − 1. Correct but wasteful: the first half of the iterations are leaves that do nothing. Start at n // 2 - 1.
Confusing the names. In CLRS, MAX-HEAPIFY(A, i) is a single sift-down and BUILD-MAX-HEAP is the loop; in Python, heapify means the whole build. Say which one you mean in an interview.
Thinking O(n) build makes heap sort O(n). The extraction phase still costs O(n log n).

Time and space complexity

Case	Time	Space	Why
Bottom-up build	O(n)	O(1)	Fewer than n swaps (the sum of node heights) and at most two comparisons per level.
n inserts, worst case	O(n log n)	O(1)	Ascending keys into a max-heap: every key climbs to the root.
n inserts, random keys	O(n) average	O(1)	Most new keys stop after a level or two.
One sift-down at height h	O(h)	O(1)	At most h swaps; O(log n) for the root.

Build Heap in Python

def build_heap(a):
    n = len(a)
    # a[n // 2:] are leaves, already heaps
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)


def sift_down(a, i, n):
    # sink a[i] inside the heap a[0:n]
    while 2 * i + 1 < n:
        l, r = 2 * i + 1, 2 * i + 2
        largest = l
        if r < n and a[r] > a[l]:
            largest = r
        if a[i] >= a[largest]:  # in order
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Why is build-heap O(n) and not O(n log n)?

Sift-down costs the height of the node it starts from, and most nodes are near the bottom: half are leaves, a quarter have height 1, an eighth height 2. Summing height × count over all levels gives less than n, so the whole build makes fewer than n swaps.

What is the difference between heapify and build-heap?

It depends on the source. In CLRS, heapify (MAX-HEAPIFY) is the O(log n) sift-down of one node and build-heap is the O(n) loop that calls it for every internal node. In Python's heapq and in everyday speech, "heapify" usually means the whole O(n) build.

Why does build-heap start at index n/2 − 1?

Index ⌊n/2⌋ − 1 is the last node that has a child, because its left child 2i + 1 is still inside the array. Every later index is a leaf, and a single node is already a heap, so there is nothing to do there.

Is building a heap by repeated insertion O(n log n)?

In the worst case, yes: inserting ascending keys into a max-heap makes every key climb to the root, Θ(n log n) in total. On random input the average is O(n), but bottom-up build-heap guarantees O(n) on every input.

Can build-heap be done in place?

Yes. It only swaps elements within the original array and keeps a couple of index variables, so it uses O(1) extra memory — one reason heap sort needs no auxiliary array.

Keep learning

Last updated 19 October 2026