Building a Heap: Bottom-Up Heapify

## The two routes into a heap A binary heap is a complete tree stored implicitly in an array, where every parent's key stands in a fixed relation to its children's (largest-at-top for a max-heap, smallest-at-top for a min-heap). There are exactly two ways to get n items into one, and interviewers ask about the difference because the costs are not the same. **Route 1 — repeated insertion.** Append the new item at the first free slot, then sift it up: while it out-ranks its parent, swap the two and move up a level. One insert is O(log n) in the worst case, because the tree of n nodes has height about log2(n) and a new item may travel all the way to the root. Doing this n times gives an O(n log n) worst-case bound for construction. **Route 2 — bottom-up (Floyd) build.** Drop all n items into the array in whatever order they came, then repair. Walk the internal nodes from the last one backwards to index 0, and sift each one *down*: compare it against its children, swap it with the stronger child if it loses, and keep descending until it sits above both children or reaches the bottom. When the loop reaches index 0 the whole array satisfies the heap property. This costs O(n) total. ## Why route 2 is cheaper The intuition is that the two routes charge work against different quantities. Sift-up costs are proportional to a node's **depth** (distance from the root), and in a complete tree most nodes are deep — about half of them are leaves at maximum depth. Sift-down costs are proportional to a node's **height** (distance to the deepest leaf below it), and by the same token most nodes have tiny height: leaves have height 0 and do no work at all, and only the single root can pay the full log n. Summing height over all nodes gives a total bounded by roughly n, whereas summing depth gives roughly n log n. So the bulk build is not a trick that makes each operation faster. Individual sift-downs still cost up to O(log n); there are simply very few expensive ones. ## When you cannot use the bulk build The linear build requires the whole collection up front, in an array you are allowed to rearrange. If pending records trickle in over the course of a day, or arrive on a stream you cannot buffer, there is nothing to heapify and the insert loop is the correct — indeed the only — answer. Similarly, if the caller hands you a collection that must keep its original order, you need a copy first, and that copy costs O(n) anyway. A related nuance: it is no accident that mainstream standard libraries expose a bulk heap-construction entry point separately from a per-element push — the heap modules shipped with both Python and C++ offer a linear-time build distinct from the logarithmic push, precisely because the two costs differ and library authors did not want callers to pay the wrong one. ## What the result is, and is not The output of a bulk build is a valid heap, not a sorted array. Only the root is guaranteed to hold the extreme key; siblings are unordered relative to each other, and an element deep in the array may out-rank an element earlier in it as long as it does not out-rank its own ancestors. Candidates who claim the build "sorts" the data are confusing construction with the repeated-extraction phase that comes later in an entirely different algorithm. The two routes also generally produce **different arrays**. Both satisfy the heap property, but the exact permutation depends on the path taken, so no test should assert on the full array contents — assert on the invariant and on what comes off the top. ## Space An iterative sift-down uses O(1) auxiliary space, so the bulk build is genuinely in place: the array you read the records into is the heap. A recursive sift-down adds O(log n) stack. The insert loop, by contrast, typically grows a container as it goes, with the reallocation and copying that implies. ## The wrong answers to avoid "Both are O(n log n) anyway" is the classic miss — it treats the bulk build as an insert loop wearing a different name. "Heapify sorts the array" is the second. "You need a second array" is the third. And the reverse error, claiming inserts are always the wasteful choice, misses that streaming arrival leaves you no alternative.