Building a Heap in O(n)

August 2026 · 19 min read

You have n elements in an array and you want a heap. The obvious route is to push them one at a time: n pushes at O(log n) each, so O(n log n). That is a correct algorithm and it is also strictly worse than necessary. You can heapify an arbitrary array in O(n) — linear, not linearithmic — and the proof is one of the nicest short arguments in elementary algorithms.

Floyd's Algorithm

The insight is to build bottom-up rather than top-down, and to use sift_down rather than sift_up.

Start from the observation that every leaf is already a valid heap — a single node trivially satisfies the parent-child rule, because it has no children. In the array encoding, the leaves are exactly the indices from n/2 to n-1. That is half the array already done, for free, before you execute a single instruction.

So begin at the last internal node, n/2 - 1, and walk backwards to the root. At each node, both of its subtrees are already valid heaps (because you processed them earlier, working backwards), which is exactly the precondition sift_down requires:

void build_heap() {
    if (a.size() < 2) return;
    for (std::size_t i = a.size() / 2; i-- > 0; )
        sift_down(i);
}

The i-- > 0 idiom is the standard way to loop an unsigned index down to and including 0 without the underflow trap from Part 3: the comparison uses the pre-decrement value, so the body runs with i from n/2 - 1 down to 0, and the loop exits cleanly when i would wrap.

A Trace

Heapify [9, 4, 7, 1, 8, 3] into a min-heap. Here n = 6, so the leaves are indices 3, 4, 5 and we start at index 6/2 - 1 = 2.

start            [9, 4, 7, 1, 8, 3]

i=2  node 7, child 3           3 < 7  -> swap
                 [9, 4, 3, 1, 8, 7]

i=1  node 4, children 1, 8     1 < 4  -> swap
                 [9, 1, 3, 4, 8, 7]

i=0  node 9, children 1, 3     1 < 9  -> swap, continue at index 1
     node 9, children 4, 8     4 < 9  -> swap
                 [1, 4, 3, 9, 8, 7]     valid min-heap

Four swaps. Note that only the root required a multi-level descent; the other two nodes stopped after one step. That is not luck — it is the whole reason the algorithm is linear.

Why It Is O(n)

The naive bound says: n/2 internal nodes, each costing up to O(log n), therefore O(n log n). That bound is valid but wildly loose, because it charges every node the cost of the tallest possible descent. Almost no node is tall.

Count properly. A node at height h (distance to its deepest leaf) costs O(h), because sift-down can descend at most h levels. And in a complete tree of n nodes there are at most ceil(n / 2^(h+1)) nodes of height h. So the total work is:

       H                        H
      sum  (n / 2^(h+1)) * h  =  n * sum  h / 2^(h+1)
      h=0                        h=0

                              <= n * sum_{h=0..inf} h / 2^(h+1)

                               = n * (1/2) * sum_{h=0..inf} h / 2^h

                               = n * (1/2) * 2

                               = n

using the standard identity sum_{h>=0} h * x^h = x / (1-x)^2, which at x = 1/2 gives (1/2)/(1/4) = 2. So the total is bounded by n swaps — O(n).

Why sift-up Bottom-Up Does Not Work

A natural question: could we go top-down with sift_up instead and get the same bound? No — and the reason is precisely the mirror image of the argument above.

Sifting up from every node costs O(depth), and the node counts are stacked the wrong way: half the nodes are leaves, and leaves have the greatest depth. So instead of a convergent series you get

sum over nodes of depth  =  n/2 * log n  +  n/4 * (log n - 1) + ...  =  Theta(n log n)

The two approaches are not symmetric because a complete binary tree is not symmetric: it has many cheap nodes at the bottom and few expensive ones at the top. Sift-down puts the expensive operation where the nodes are rare; sift-up puts it where they are abundant. That is the whole difference between O(n) and O(n log n) here.

When the Difference Is Real

If you have all n elements up front, always heapify — it is a one-line change for an asymptotic win. In C++ that means constructing from a range rather than pushing in a loop:

#include <queue>
#include <vector>
#include <algorithm>

std::vector<int> data = load();

// O(n log n): n separate pushes
std::priority_queue<int> slow;
for (int x : data) slow.push(x);

// O(n): range constructor calls std::make_heap internally
std::priority_queue<int> fast(data.begin(), data.end());

// O(n) in place, if you want the heap in your own vector
std::make_heap(data.begin(), data.end());

The difference shows up clearly at scale — for a few million elements the range constructor is comfortably faster, and it is also less code. The usual caveat applies: if elements arrive one at a time, you have no choice but to push, and O(n log n) total is unavoidable.

Next

We have now written every part of a binary heap by hand. Part 5 maps all of it onto what the standard library already gives you — std::priority_queue, the std::*_heap algorithm family, and the comparator conventions that decide whether you get a min-heap or a max-heap.