Question bank — Heapify — bottom-up O(n) build

True. A leaf has no children, so it cannot violate parent≥child; calling siftDown on it is wasted work and could even index a child past the array end (out of bounds).

False. A single siftDown can cost up to $O(\log n)$ (the root's). The total is $O(n)$ because tall, expensive nodes are exponentially rare — not because any one call is cheap.

False. It is a correct upper bound — just not a tight one. Every node truly costs at most $O(\log n)$, so the sum is at most $O(n\log n)$; the sharper analysis shows it's actually $O(n)$.

True. That value $2$ is derived in the Why questions section below (differentiate the geometric series, then plug $x=\frac{1}{2}$). Because the weighted sum is a finite constant independent of $n$, the total work is $\frac{n}{2}\cdot 2=O(n)$; the "$\log$" you'd expect gets killed by the exponentially shrinking node counts.

False. Insertion build is $O(n\log n)$. siftUp moves the numerous leaves toward the root — the expensive direction — whereas siftDown pushes expensive travel onto the rare tall nodes.

False. It only satisfies the heap property (parent≥children in a max-heap). The largest element sits at index 0, but the rest are only partially ordered; sorting requires Heapsort on top.

False. Both yield a valid heap, but the arrangements can differ. Many valid heaps exist for one multiset; the two algorithms take different swap paths.

False. In this analysis height is counted from the bottom: leaves = height 0, root = height $h$. Counting from the top is depth, and the cost argument breaks if you mix them up.

True. Since the cost is $\Theta (n)$, work scales linearly — double the elements, double the work (asymptotically), unlike $n\log n$ which grows a bit faster.

Two errors: the start index should be the last internal node $\lfloor n/2\rfloor -1$ (leaves need no siftDown), and siftDown moves down, never toward the root.

Wrong order. siftDown(i) assumes both child subtrees are already valid heaps; going top-down violates that precondition and can leave a non-heap. You must go from $\lfloor n/2\rfloor -1$ down to 0.

They don't. Recall $l=2i+1$, $r=2i+2$: a node near the bottom may have zero, one, or two children, and those computed indices can exceed $n-1$. The l < n and r < n guards prevent reading past the array end (an out-of-bounds bug).

For a min-heap you compare for the smaller child and swap when a child is smaller than the parent — the whole comparison direction flips (and largest becomes smallest), not just one line.

The leaves are skipped as starting points, but they are still visited as children. Concretely, take [3, 9, 2] ($n=3$): the only siftDown call is on the root $i=0$, which computes $l=1$, $r=2$ and compares against both leaves 9 and 2 even though 9's subtree is a leaf. So the leaves are read via the l<n/r<n checks; the $O(n)$ bound counts that work, and the real point is that cost stays constant per node on average, not that half the nodes are ignored.

The cost is $O(k)$, not $O(2^k)$. siftDown follows a single root-to-leaf path, dropping at most $k$ levels — it does not touch the whole subtree.

$\lfloor n/2\rfloor -1$ is the parent of the last element (index $n-1$), since parent-of-$(n-1)=\lfloor (n-2)/2\rfloor =\lfloor n/2\rfloor -1$; every index above it is an internal node, every index after it is a leaf. Off-by-one here either wastes work on a leaf or skips a real internal node.

The children of node $i$ live at indices $2i+1$ and $2i+2$, both larger than $i$, so they were already processed earlier in the descending loop. Their subtrees are therefore already valid heaps — exactly what siftDown(i) needs.

Each level up the tree holds roughly half as many nodes as the level below: leaves ≈ $n/2$, height-1 ≈ $n/4$, and so on (see the second figure). So height $k$ holds ≈ $n/2^{k+1}$ — tall nodes are exponentially scarce.

We know ${\sum }_{k\ge 0}{x}^k=1/(1-x)$ in closed form, but we need a $k$-weighted version. Differentiating gives ${\sum }_{k\ge 1}k{x}^{k-1}=1/(1-x{)}^2$; multiply by $x$ to get ${\sum }_{k\ge 0}k{x}^k=x/(1-x{)}^2$. Plugging $x=\frac{1}{2}$: $\frac{1/2}{(1/2{)}^2}=\frac{1/2}{1/4}=2$. That is the finite constant that makes the whole sum linear.

There is only one root (and few near-root nodes). Their $O(\log n)$ cost, multiplied by their tiny count, contributes a bounded amount. The convergent weighted sum absorbs it into a constant.

For building from a full array, siftDown is asymptotically faster ($O(n)$ vs $O(n\log n)$). But siftUp is the right tool for incremental insertion into an existing heap, where you add one element at the bottom and float it up — see siftUp vs siftDown.

The start index is $\lfloor 1/2\rfloor -1=-1$, so the loop runs zero times. A single element is trivially a valid heap — correct, and no work needed.

Yes: the start index is $-1$, the loop body never runs, and an empty array vacuously satisfies the heap property. No crash, no swaps.

siftDown finds largest == i at every node and breaks immediately, doing zero swaps. It still visits each internal node once, so the cost is still $\Theta (n)$ comparisons — heapify does not "detect" and short-circuit an already-heaped array to $O(1)$.

No. Each siftDown step swaps with at most one child — the larger of the two (max-heap). It then continues down from that child's position, possibly swapping again, but never two swaps at the same level.

Every parent already equals (hence $\ge$) its children, so siftDown breaks at each node with no swaps. The array is a valid heap unchanged — the comparison uses $>$ (strict), so equal children never trigger a swap.