Skip to content
Essay · Complexity

Why is heapify O(n) and not O(n log n)

Why is heapify O(n) when each sift-down can cost O(log n)? Because the work per node depends on its height, and half the nodes have height zero. Here is the counting argument with real numbers, and the reason repeated insertion does not get the same bound.

By Vishy9 min readPublished · 6 Nov 2026

Why is heapify O(n) when it runs a sift-down, which costs O(log n), on roughly n/2 nodes? Because most of those nodes sit near the bottom of the tree, where a sift-down can move only a step or two. Add up the real distances instead of the worst-case ones and the total is at most about n swaps.

The first time I read this claim I did not believe it. I had a perfectly good argument for n log n, and the textbook just stated a smaller number with a sum that conveniently converged. The doubt was reasonable. The n log n argument is not wrong; it is loose. Seeing exactly where it loses precision is the whole lesson, and it transfers to other analyses where a cheap bound hides a tighter one.

What does heapify actually do?

Heapify turns an arbitrary array into a valid heap in place by running sift-down on every non-leaf node, starting from the last one and walking back toward the root. It does not insert anything and it does not sort anything.

In a zero-indexed array of n elements, the children of index i live at 2i+1 and 2i+2. That means the last node that has any child is at index n//2 - 1, and every index from n//2 to n-1 is a leaf. Leaves are already valid one-element heaps, so we skip them. For n = 15 we skip indexes 7 through 14 and start at index 6.

The order matters. When we reach index i, everything below it has already been fixed, so both subtrees hanging off i are valid heaps. The only possible violation is at i itself, and a single sift-down repairs it: swap with the smaller child (for a min-heap) and repeat until the element is smaller than both children or becomes a leaf. This is induction in disguise, which is why the correctness half of the proof is easy. The interesting half is the cost. See recursion as induction if that framing is new, and heap as array for the index arithmetic.

def sift_down(a, i, n):
    while True:
        l = 2 * i + 1
        r = l + 1
        smallest = i
        if l < n and a[l] < a[smallest]:
            smallest = l
        if r < n and a[r] < a[smallest]:
            smallest = r
        if smallest == i:
            return
        a[i], a[smallest] = a[smallest], a[i]
        i = smallest

def heapify(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)

Why does O(n log n) look right, and where is it loose?

It looks right because it is a valid upper bound: about n/2 calls, each costing at most the height of the tree, which is log n. Multiply and you get O(n log n). The bound is simply not tight, because it charges every call the cost of the worst call.

Here is the flaw. A sift-down started at node v can travel only as far as the leaves below v. Its cost is bounded by the height of v, meaning the longest path from v down to a leaf, not by the height of the whole tree. Only the root has height log n. The root is one node. Its two children have height log n - 1, and so on. The charge of log n per call is correct for exactly one call and wildly pessimistic for the others.

This is a pattern worth recognising in any analysis. Whenever you multiply a count by a maximum, ask whether the maximum is attained by most of the items or by a vanishing few. If it is a few, the sum is usually smaller than the product, sometimes by a whole logarithmic factor. I wrote about the general habit of treating a bound as a claim with conditions in complexity is a contract; heapify is a clean example of a contract whose obvious reading is too generous.

How do you count the work exactly?

You group nodes by height, not by index, and multiply the number of nodes at each height by the maximum swaps each can make. The sum turns out to be a series that converges to a constant times n.

Start with a small perfect tree, n = 15, four levels. Heights are measured from the bottom:

  • Height 0: 8 leaves, 0 swaps each, 0 total (and we never call sift-down on them).
  • Height 1: 4 nodes, at most 1 swap each, 4 total.
  • Height 2: 2 nodes, at most 2 swaps each, 4 total.
  • Height 3: 1 node (the root), at most 3 swaps, 3 total.

The worst case is 4 + 4 + 3 = 11 swaps. Compare that with the naive bound: 7 non-leaf nodes times a height of 3 gives 21, and 15 times log2(15), about 3.9, gives roughly 58. The true ceiling of 11 is a fraction of either. For a perfect tree of n = 2^k - 1 nodes the worst case works out to exactly n - k swaps, so 15 - 4 = 11, and 7 - 3 = 4 for the seven-node tree.

Now the general argument. In a heap of n nodes, there are at most ceil(n / 2^(h+1)) nodes at height h. Each costs at most h swaps. So the total is bounded by the sum over h of (n / 2^(h+1)) times h, which is n times the sum of h / 2^(h+1). That series equals 1, and here is a short way to see it. Let S be 1/2 + 2/4 + 3/8 + 4/16 and so on. Halve it to get 1/4 + 2/8 + 3/16 and so on. Subtract the second from the first and each term collapses to 1/2 + 1/4 + 1/8 + ..., which is 1. So S = 2, and the sum of h / 2^(h+1) is S / 2 = 1. The total swap count is at most n. The ceilings add a small correction of order log squared n, which is irrelevant next to n for any array big enough to matter.

Scale it up. For n = 1,000,000 the swap count is at most about 1,000,000. Each level of a sift-down does two comparisons (one between the children, one against the moving element), so you are looking at no more than about 2,000,000 comparisons. The sloppy bound would have said 1,000,000 times 20, or 20 million. That is a factor of ten, and it comes entirely from noticing where the nodes live.

Why doesn't inserting n items one at a time give the same bound?

Because insertion sifts up, and sift-up cost is bounded by depth, not height. Half the nodes sit at the deepest level, so half of them can each travel about log n steps. The same tree, measured with a different ruler, gives a different sum.

Here is the framing I use. Picture a tower where every resident pays a fee proportional to the number of floors they might have to travel. Half the residents live on the ground floor. In the sift-down scheme, a resident can only be sent down from where they live, so the ground-floor residents owe nothing and the penthouse resident owes the most. In the sift-up scheme, a resident can only be sent up, so the ground-floor crowd owes the most, up to the full height of the tower. Same building, same people, opposite billing direction. Heapify bills the few at the top for long trips. Repeated insertion bills the many at the bottom.

Concretely, take n = 1,000,000 and push values in descending order into a min-heap. Each new value is smaller than everything present, so it rises all the way to the root. Roughly half the pushes land at depth 19 or so and travel that far. The total is about n times (log2 n - 1), near 19 million swaps. Compare that with heapify's 1 million on the same data. Not a rounding error: a factor of nineteen.

One caution, because this surprises people. On random input, repeated insertion also averages O(n), since a random new value usually stops after a step or two. So if you benchmark both on shuffled data you may see them close together. The distinction is in the worst case, and heapify has no bad input that costs more than about n swaps. If you want guarantees, you want the bottom-up build.

How does heapify compare with the alternatives?

Heapify is the cheapest way to get a valid heap from unordered data, and it is the only one with a linear worst case. Sorting also produces a valid heap, but it pays for far more order than a heap needs.

ApproachWorst caseNotes
Push one at a time (sift-up)O(n log n)Average on random data is O(n); descending input into a min-heap hits the worst case
Bottom-up heapify (sift-down from n//2 - 1)O(n)At most about n swaps and 2n comparisons; in place
Sort the arrayO(n log n)A sorted array is a valid min-heap, but you paid for total order
Heapify, then pop k timesO(n + k log n)Good when k is much smaller than n; see top-k selection

Every mainstream library exposes this. Python has heapq.heapify(list), Java's PriorityQueue has a constructor that accepts a collection and builds bottom-up, and C++ has std::make_heap. When you already hold all the data, calling these once beats looping over push, and the code is shorter too.

The payoff shows up in top-k work. Say you have 1,000,000 numbers and need the 10 largest. Heapify the whole array as a max-heap for roughly 2 million comparisons, then pop 10 times at about 40 comparisons each, so a few hundred more. Sorting the array first costs close to n log2 n, about 20 million comparisons. That is the practical case for a heap over a sort, and I go through the decision more carefully in when should you use a heap instead of sorting. If you do not need a heap afterward at all, quickselect gets the kth element in expected linear time without building one.

Where does the proof usually go wrong?

It goes wrong in four predictable places, and each one is worth checking when you reconstruct the argument under interview pressure.

  • Counting by depth instead of height. If you charge each node its depth, you are analysing sift-up and will land on n log n. Sift-down is charged by height.
  • Starting the loop at the wrong index. Starting at n-1 is harmless but wasteful, since leaf calls return immediately. Starting at n//2 or higher misses a parent and silently leaves the array invalid. The last parent is n//2 - 1 in zero-indexed form.
  • Looping in the wrong direction. Going from the root down to the leaves, with sift-down at each step, breaks the induction. The subtrees are not yet heaps, so one sift-down is no longer enough.
  • Concluding that heapsort is linear. Heapsort builds the heap in O(n), then extracts n times at O(log n) each. The extraction phase is still n log n. The build phase is cheap, but it is the smaller half of the work.

There is also a small honesty point about the constant. The statement is that the build is O(n), not that it is exactly n. The exact count depends on the tree shape and the data, and the bound of about 2n comparisons is a ceiling, not a typical figure. If you quote a number in an interview, say "at most about 2n comparisons" and you will be correct.

I find this result useful beyond heaps. The pattern, where the number of items shrinks geometrically as the per-item cost grows arithmetically, shows up in dynamic arrays, in tournament trees, and in the analysis of building segment trees. Whenever you see work that doubles in cost while halving in count, you are probably looking at a convergent series and a linear total. The same idea underlies the argument in what is amortized time complexity, where occasional expensive steps are paid for by many cheap ones.

Frequently asked questions

Is heapify the same thing as build-heap?

Yes, in most texts the two names refer to the bottom-up procedure that sifts down from the last parent to the root. Some sources use "heapify" for a single sift-down on one node, so check the definition. The O(n) result applies to the full bottom-up loop, not to a single call.

Why do we start at index n//2 - 1 and not at the root?

Starting at the last parent guarantees that both subtrees of the node you are fixing are already valid heaps, so one sift-down is enough. Starting at the root would force repeated repair work because nothing beneath it is ordered yet. Indexes from n//2 onward are leaves and need no work.

Does a linear heapify make heapsort O(n)?

No. Heapsort still has to remove the maximum n times, and each removal costs O(log n), so the total remains O(n log n). The linear build only speeds up the first phase. To practise the case where the cheap build really does pay off, try Kth Largest Element.