Heapify — bottom-up O(n) build: Visual walkthrough

Step 1 — The array is a tree (see the shape)

WHAT. We have a plain list of numbers, A[0], A[1], A[2], .... We agree to read it as a triangle: A[0] on top, the next two below it, the next four below that, and so on. This triangle is called a Complete Binary Tree — "complete" meaning every row is full except possibly the last, which fills left-to-right.

WHY. Nothing in memory is actually shaped like a triangle. But if we pretend it is, then the phrase "the children of a node" becomes a simple arithmetic rule on indices — no pointers, no wasted memory. That pretending is the whole trick of a heap.

PICTURE. Below, the same six numbers appear twice: as a flat row (how they live in memory) and as the triangle (how we think about them). The colored arrows show that index $0$ 's two children are indices $1$ and $2$ .

Step 2 — Height: measuring from the bottom

WHAT. We label every node with its height $k$ = how many levels it sits above the very bottom row. Leaves (the bottom row) have $k = 0$ . Their parents have $k = 1$ . The root has the biggest height, which we call $h$ .

WHY. We measure from the bottom, not the top, because the cost of fixing a node depends on how far down it can fall — and a node can fall at most as many levels as it has below it. That number is exactly its height $k$ .

PICTURE. The tree is painted in horizontal bands. Read the height label on the left of each band. Notice: the bottom band is the widest (most nodes), the top is a single dot.

Step 3 — One `siftDown` costs its own height

WHAT. To fix a node, we run siftDown. One loop iteration does a fixed chunk of work: it looks at the node's two children, picks the larger (that's up to two comparisons), compares against the parent, and maybe swaps. Crucially this chunk is bounded by a constant — at most 2 comparisons + 1 swap, no matter where in the tree we are. We call one such iteration a basic operation; that is our unit of cost. siftDown repeats this iteration, walking one level down each time.

WHY. Because a single iteration is a fixed-size chunk (constant work), we can just count iterations and multiply by that constant at the end — the constant is exactly what $O (\cdot)$ hides. A node at height $k$ has $k$ bands beneath it, so in the worst case it runs at most $k$ iterations (one per level descended). Hence its cost is $O (k)$ .

PICTURE. A single node (the plum dot) sinks down the arrows. Count the arrows — that count is $k$ , the number of iterations. A leaf ( $k = 0$ ) has zero arrows: zero descending iterations.

Step 4 — Count how many nodes live at each height

WHAT. Now count the nodes band by band. The bottom band (height 0) holds about half of all nodes: $n /2$ . The next band up (height 1) holds about a quarter: $n /4$ . Each step up halves the population.

WHY. Every node in a band is the parent of (up to) two nodes in the band below. So each band has roughly half as many nodes as the one beneath it. That halving is the secret weapon: tall nodes are exponentially rare.

PICTURE. The same banded tree, now with a count label on each band: $n /2$ , $n /4$ , $n /8$ , … shrinking to $1$ at the top. The area of each band shrinks by half as you climb.

Step 5 — Multiply count × cost, then add it all up

WHAT. First we pin down what "total work" means. Define $T (n)$ = the total number of siftDown iterations performed by buildHeap on an array of $n$ nodes. It is: for each band, (how many nodes) × (iterations per node), summed over all bands from $k = 0$ to $h$ .

WHY. Total work is just the sum of everyone's individual work, and we count it in the one unit fixed in Step 3 — siftDown iterations. We already know each of the two factors from Steps 3 and 4 — now we assemble them, keeping the constants explicit so no $O (\cdot)$ is smuggled through a sum.

PICTURE. A stacked-bar chart: one bar per height. Bar width shrinks (fewer nodes) while the per-node cost grows (taller sink). The area of each bar is that band's total contribution — and the areas peak low and then vanish.

Step 6 — Why we reach for calculus (the $\sum k x^{k}$ tool)

WHAT. We must evaluate $\sum_{k = 0}^{\infty} k / 2^{k}$ . This is a Geometric Series but with an extra factor of $k$ glued onto each term. Plain geometric-series formulas don't have that $k$ .

WHY THIS TOOL. Where does an extra factor of $k$ come from? From differentiating $x^{k}$ : the power rule gives $\frac{d}{d x} x^{k} = k x^{k - 1}$ , and out pops a $k$ . So differentiation is precisely the machine that turns a $k$ -free series into a $k$ -weighted one. That's why we differentiate — no other elementary operation manufactures that $k$ so cleanly.

PICTURE. Two number-lines of terms: the plain geometric series $1, x, x^{2}, \dots$ on top; below it the differentiated one $1, 2 x, 3 x^{2}, \dots$ with the freshly-created coefficients $1, 2, 3, \dots$ circled in orange — you can see the $k$ appear.

Step 7 — Plug in $x = \frac{1}{2}$ : the magic constant

WHAT. Our sum uses $x = \frac{1}{2}$ (because $1/ 2^{k} = (1/2)^{k}$ ). Substitute into the identity.

WHY. This turns an infinite sum into a single finite number — and that number does not depend on $n$ . A constant. That constant is the entire reason the $lo g$ disappears.

PICTURE. The infinite series drawn as shrinking blocks $0 + \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \dots$ stacking up and pressing against a ceiling line at height $2$ — they converge, never passing it.

Feed this back into Step 5:

T (n) \leq c_{0} n \cdot 2 = 2 c_{0} n = O (n) .

Step 8 — Edge & degenerate cases (nothing left unshown)

WHAT. We check the corners so no reader hits an unshown scenario.

WHY. A proof that only works for "nice" $n$ isn't a proof. Here are every boundary case.

$n = 0$ or $n = 1$ : last internal node is $⌊ n /2 ⌋ - 1 = - 1$ or $- 1$ . The loop for i from -1 down to 0 runs zero times — a single node (or empty array) is already a heap. No work, consistent with $T \leq O (n)$ .
The last band may be half-empty. In a near-complete tree the bottom row isn't full. That only makes the counts $n / 2^{k + 1}$ over-estimates (we used $\leq$ and $⌈ ⌉$ ), so the bound still holds — it never breaks in our favor.
All-equal array (e.g. [5,5,5,5]): every siftDown finds largest == i immediately and breaks — best case, still $\leq O (n)$ .
Already-sorted descending array = already a max-heap: every node breaks instantly. Worst travel never happens; linear bound is loose but correct.

PICTURE. Three tiny trees side by side: $n = 1$ (single dot, "nothing to do"), a half-filled bottom row (crossed-out ghost leaves showing over-count), and an all-equal tree (every arrow marked "no swap").

The one-picture summary

Everything above, compressed: wide-and-cheap at the bottom, narrow-and-expensive at the top, and the total area is finite because the widths halve faster than the costs grow.

Recall Feynman: the whole walkthrough in plain words

Picture a crowd arranged as a pyramid. The bottom rows are packed with people, but each of them barely has to move — they're already near where they belong (cost near zero). As you climb, there are fewer and fewer people, and only those few have a long way to travel. To find the total effort, we multiply "how many people are on each row" by "how far each must move," and add up the rows. The far-travelers are so rare (each row up has half as many people) that when you add every row's effort together, it stops growing — it settles on a fixed multiple of the crowd size. We proved it settles by borrowing one trick from calculus: differentiating the geometric series conjures the exact weighting we needed, and plugging in one-half gives the clean number 2. Two times half the crowd is just the crowd — so building a heap is linear.

Recall

Total work formula for build-heap? ::: $T (n) = \sum_{k = 0}^{h} \frac{n}{2 ^{k + 1}} \cdot O (k)$ , count times cost per band. Which calculus operation creates the factor $k$ , and why use it? ::: Differentiation of $x^{k}$ gives $k x^{k - 1}$ ; it's the only elementary move that manufactures the $k$ -weighting we need. Value of $\sum_{k = 0}^{\infty} k / 2^{k}$ ? ::: Exactly $2$ (plug $x = 1/2$ into $x / (1 - x)^{2}$ ). What does $O (n)$ count on this page? ::: The number of siftDown loop iterations, bounded by a constant times $n$ . What happens for $n = 0$ or $n = 1$ ? ::: Start index is $- 1$ ; the loop runs zero times — already a heap.