Bottom-Up Heap Construction in Linear Time

Given an array of n unordered keys, producing a valid heap looks like it should cost what n insertions cost: each insertion sifts up through at most ⌊log₂ n⌋ levels, so the total is O(n log n). That bound is correct for the insertion path and wrong for the problem. When all keys are available at once, a heap can be built in Θ(n) total work — linear, not linearithmic — by repairing the array from the bottom up. The technique is usually called heapify or Floyd’s method, and the argument for why it is linear is a counting argument over tree levels that is worth knowing in full, because the same shape of argument bounds several other bulk-structure builds.

The observation that half the array is already done

In a complete binary tree with n nodes, every node at index ⌊n/2⌋ or above is a leaf. A leaf has no children, so it vacuously satisfies the heap property: there is nothing below it that could be larger. For n = 1,000,000 that is 500,000 nodes that need no work at all, and the array is already half finished before anything is compared.

The remaining nodes are internal, and each has at least one child. Process them in decreasing index order, from ⌊n/2⌋ − 1 down to 0, calling sift-down on each. When sift-down runs on index i, both subtrees of i are already valid heaps, because every index greater than i has been processed already and every child index is greater than its parent’s index in the level-order numbering. Sift-down therefore restores the invariant at i given that its subtrees satisfy it — precisely the precondition the routine needs.

/* Repairs the subtree rooted at i, assuming both children of i are already heaps. */
static void sift_down(int *a, size_t n, size_t i) {
    for (;;) {
        size_t l = 2 * i + 1, r = l + 1, m = i;
        if (l < n && a[l] < a[m]) m = l;
        if (r < n && a[r] < a[m]) m = r;
        if (m == i) return;
        size_t t = a[i]; a[i] = a[m]; a[m] = t;
        i = m;
    }
}

void build_heap(int *a, size_t n) {
    if (n < 2) return;
    /* Start at the last internal node; indices >= n/2 are leaves, which are trivially heaps. */
    for (size_t i = n / 2; i-- > 0; )
        sift_down(a, n, i);
}

The loop runs ⌊n/2⌋ times, so the number of sift-down calls is linear. The cost of each call is not constant, which is where the naive reading goes wrong: multiplying a linear number of calls by a logarithmic worst case per call gives O(n log n) and throws away the fact that most of those calls are on nodes near the bottom, which have almost no height left to descend.

Counting work per level, not per call

Let h be the height of a node, meaning the number of edges on the longest downward path from it to a leaf. Sift-down on a node of height h performs at most h steps, each costing at most two comparisons — one to choose the smaller child, one to decide whether to swap.

In a complete binary tree of n nodes, the number of nodes of height h is at most ⌈n / 2^(h+1)⌉. The count follows by stripping leaves. Removing every leaf from a complete tree leaves a complete tree on ⌊n/2⌋ nodes — the parents of the leaves, in the same relative order — and a node of height h in the original becomes a node of height h − 1 in the stripped tree. So the count of height-h nodes in n nodes equals the count of height-(h−1) nodes in ⌊n/2⌋ nodes, and induction on h reduces the bound to the base case, which is just the leaf count of a complete tree: at most ⌈n/2⌉ nodes of height 0, giving the bound ⌈n / 2^(h+1)⌉.

Total work is then bounded by the sum over heights:

$$ \sum_{h=0}^{\lfloor \log_2 n \rfloor} h \cdot \frac{n}{2^{h+1}} ;=; \frac{n}{2} \sum_{h \ge 0} \frac{h}{2^h} ;=; \frac{n}{2} \cdot 2 ;=; n $$

using the identity Σ h/2^h = 2. The sum converges because each successive level contributes half as many nodes at one more unit of per-node cost: the level with n/4 nodes of height 1 does n/4 units of work, the level with n/8 nodes of height 2 does n/4 units, the next does 3n/16, and the series is dominated by its first few terms. Constant factors from the two-comparisons-per-level accounting push the total to roughly 2n comparisons in the worst case, still linear.

The bound is not merely an upper bound that happens to hold. Building a heap by this method on an array arranged so that every sift-down descends the full height of its node does the work the sum describes, which is Θ(n). Nothing can beat that, since every key must be read at least once.

Why the mirror-image procedure is not linear

The symmetry is tempting: instead of sifting down from the bottom, sift up from the top, processing indices in increasing order and calling sift-up on each. Correctness holds — when sift-up runs on index i, the path from the root to i’s parent is already a valid heap — but the cost does not.

The node counts invert. Sift-up on a node at depth d costs at most d steps, since the path to the root has d edges. A complete tree has at most 2^d nodes at depth d, so the total over all depths is bounded by

$$ \sum_{d=0}^{\lfloor \log_2 n \rfloor} d \cdot 2^d ;<; (H - 1) \sum_{d=0}^{H} 2^d ;<; (H - 1) \cdot 2^{H+1} ;\le; 4 n \log_2 n $$

with H = ⌊log₂ n⌋, using d < H for every term except the last. The total is Θ(n log n), and it is exactly the cost of n successive insertions, because that is what the procedure is. The deepest level, which holds about half the nodes, contributes more than half the total on its own. The bottom-up method wins not by a better inner loop but by attacking the many cheap nodes instead of the few expensive ones.

The practical consequence is a rule about when each applies. Insertion is the only option when keys arrive one at a time and the heap must be queryable between arrivals. When a complete input is available — a batch of scheduled jobs read from a file, the vertices of a graph loaded before a search begins — bulk construction is strictly better and requires no extra memory.

Edge cases and the shape of the input

Three boundary conditions deserve attention in an implementation.

The empty and single-element cases must be handled before the loop, because n / 2 is 0 for n = 1. The decrementing form for (i = n/2; i-- > 0; ) handles that by testing before decrementing and terminates when the index reaches zero, whereas for (i = n/2 - 1; i >= 0; i--) on an unsigned index executes i = SIZE_MAX and runs off the array. That wrap is the single most common defect in hand-written heap code.

Duplicates require no special handling. The invariant constrains comparisons, not identity, so equal keys may be arranged in any order consistent with the parent-child relation, and sift-down’s choice between two equal children is arbitrary.

A comparator that is not a strict weak ordering breaks the build silently. Because the precondition “both subtrees are already heaps” is never checked, an inconsistent relation produces an array that looks like a heap to the algorithm and fails the invariant when tested. There is no cheap runtime detection; the structure trusts the relation supplied to it.

The number of comparisons is not the only cost. For large elements the moves dominate, and the level-order layout means a sift-down near the root touches one element per level, spread across the array at exponentially increasing strides — index 0, then 1 or 2, then 3 to 6, then 7 to 14. The first few levels share cache lines; the last few do not. Bulk construction touches every element once or twice, which is close to the minimum possible traffic over the array and is one reason it is the preferred way to load a large heap regardless of the asymptotic argument.

Bulk construction also composes with other heap shapes. The same bottom-up repair works for a heap with any fixed branching factor, since the precondition only needs the children processed before the parent; the level-counting argument changes with the branching factor but the linear bound survives, as d-ary heaps and branching factor sets out. For structures that support merging rather than in-place repair, bulk loading means merging single-node heaps one at a time, and the cost of that merge is what separates the designs described in melding with leftist and skew heaps.