Heapify — bottom-up O(n) build: Foundations — Coding deep dive

This page assumes you know nothing. Every symbol the parent note (Heapify — bottom-up O(n) build) throws at you is built here from the ground up, in an order where each idea leans on the one before it. Read top to bottom.

1. The array — a row of numbered boxes

Before any "tree" talk, the raw material is an array: a straight row of storage boxes, each holding one number, each with an index (a position label).

Figure s01 — an array as numbered boxes. Seven values sit in a row; below each box is its index label i=0, 1, 2, …. The orange arrow points at box $2$ to show what A[2] names; the green and red captions mark the first box (index $0$ ) and the last box (index $n - 1$ ). Use it to see that "value" and "position" are two different things.

$n$ ::: the count of items in the array (how many boxes).
$A [i]$ ::: the value in box number $i$ .

The topic needs this because a heap is secretly just this array — no pointers, no tree objects, only boxes and index math.

2. The complete binary tree — reading the row as a triangle

Now the magic reinterpretation. We take that flat row and draw it as a triangle where the first box is at the top, the next two below it, the next four below those, and so on.

Figure s02 — the same row read as a tree. The top strip is the flat blue row of seven numbers; below it the identical seven numbers appear as circles wired into a triangle. Blue circles are internal nodes, green circles are leaves, each labelled with its index i=…. The orange arrow marks the root (index $0$ ). Notice the wires: index $0$ connects down to indices $1$ and $2$ ; index $1$ down to $3$ and $4$ — this is the index map of §3 drawn as lines. Nothing is copied — the triangle is just a way of looking at the same row.

3. The index map — the arithmetic that glues array to tree

Here is why the "no gaps" rule matters: it lets us jump between a node and its family using only arithmetic, no stored links. Before the formula, we need one symbol.

Now, with $⌊ ⌋$ already in hand, the map:

Why the topic needs this: siftDown walks down the tree, so it must compute a node's children instantly — that's the $2 i + 1$ / $2 i + 2$ jump.

4. Which boxes are leaves? The start index $⌊ n /2 ⌋ - 1$

Let us actually solve "which is the last node that still has a child?" — the WHY behind $⌊ n /2 ⌋ - 1$ :

Figure s03 — where the leaves begin. A 6-node tree: orange circles are internal nodes ( $i = 0, 1, 2$ ), green circles are leaves ( $i = 3, 4, 5$ ). The red arrow lands on index $2 = ⌊ 6/2 ⌋ - 1$ , the last node with a child — build-heap starts sifting here and skips everything to its right. Trace it: node $2$ 's left child would be $2 (2) + 1 = 5$ , which still fits ( $5 \leq 5$ ); node $3$ 's would be $7$ , which falls off — so $3$ is a leaf.

last internal (non-leaf) node ::: index $⌊ n /2 ⌋ - 1$ .
The topic starts heapify here because leaves are already valid heaps (nothing below them to violate anything), so sifting them is wasted work.

5. The heap property — the rule the whole game enforces

The symbol $\geq$ means "greater than or equal to"; $\leq$ means "less than or equal to." Picture water finding its level: in a max-heap the biggest value bubbles to the top; in a min-heap the smallest does. The root therefore always holds the extreme value — the reason heaps power a Priority Queue and Heapsort.

6. `siftDown` — pushing a misplaced value to its level

Why "down" and why upward processing? siftDown(i) only works if the stuff below $i$ is already tidy. Processing nodes from the last internal one up to the root guarantees that when we reach $i$ , its children were fixed earlier — a small bottom-up dynamic-programming order.

7. Height, and counting nodes per height

The parent measures height from the bottom to reason about total cost later.

Now the counting claim that later carries the whole linear-time proof — with its WHY spelled out:

Intuition Why at most

$\approx n / 2^{k + 1}$ nodes sit at height $k$ Build the count from the bottom, using the doubling rule in reverse.

Leaves (height $0$ ). In a full tree the bottom row is as wide as all the rows above it put together, plus one: rows above hold $1 + 2 + 4 + \dots = (bottom width) - 1$ nodes. So the bottom row alone is about half of everything: $\approx n /2 = n / 2^{0 + 1}$ .
Height $1$ . Each height- $1$ node is the parent of (up to) two leaves, so there are about half as many of them as leaves: $\approx n /4 = n / 2^{1 + 1}$ .
Height $k$ . Repeating "each step up roughly halves the count" $k$ times from the $n /2$ leaves gives $\approx n / 2^{k + 1}$ .

The picture: a triangle whose rows double going down means the count halves going up, so tall nodes are exponentially rare — the heart of the linear-time result (fully expanded via Geometric Series and Amortized Analysis).

What does $A [i]$ mean, and where does counting start? ::: The value in box $i$ ; indices start at $0$ , last is $n - 1$ .
What is a complete binary tree? ::: A tree filled row by row, left to right, with no gaps — so it maps onto an array with no wasted boxes.
What does $⌊ x ⌋$ do? ::: Rounds $x$ down to the nearest whole number.
Given node $i$ , its left child, right child, and parent indices? ::: $2 i + 1$ , $2 i + 2$ , and $⌊(i - 1) /2 ⌋$ .
Which index is the last internal (non-leaf) node, and why? ::: $⌊ n /2 ⌋ - 1$ ; solving $2 i + 1 \leq n - 1$ gives $i \leq n /2 - 1$ , so everything after it is a leaf.
What happens for $n = 0$ or $n = 1$ ? ::: The start index is $- 1$ , so the loop never runs — empty and single-node arrays are already valid heaps.
State the max-heap property. ::: Every parent $\geq$ both of its children (min-heap: parent $\leq$ children).
What must be true before calling siftDown(i)? ::: Both of $i$ 's children's subtrees are already valid heaps.
What does $lo g_{2} n$ compute? ::: The power of $2$ that gives $n$ — roughly the tree's height in rows.
Roughly how many nodes sit at height $k$ , and why? ::: At most $n / 2^{k + 1}$ — the bottom row is ~half the tree and each step up halves the count, so tall nodes are exponentially rare.
What is the difference between $O (n)$ and $O (n lo g n)$ ? ::: A straight line vs a line bent slightly upward by the $lo g$ factor.

Foundations — Heapify — bottom-up O(n) build

1. The array — a row of numbered boxes

2. The complete binary tree — reading the row as a triangle

3. The index map — the arithmetic that glues array to tree

4. Which boxes are leaves? The start index $⌊ n /2 ⌋ - 1$

5. The heap property — the rule the whole game enforces

6. `siftDown` — pushing a misplaced value to its level

7. Height, and counting nodes per height

8. Big-O — what " $O (n)$ " and " $O (n lo g n)$ " mean

Prerequisite map

Equipment checklist