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

(a) $h=\lfloor {\log }_{2}11\rfloor =\lfloor 3.459\rfloor =3$. (b) Start index $=\lfloor 11/2\rfloor -1=5-1=4$. So we sift nodes $4,3,2,1,0$. (c) Everything from the start index $+1$ to the end is a leaf: indices $5,6,7,8,9,10$ → that is $11-5=6$ leaves. Check: internal nodes $=$ indices $\mathrm{0..4}=5$; leaves $=6$; $5+6=11$ ✓.

Index $1$ has value $10$.

• parent index $=\lfloor (1-1)/2\rfloor =0$ → value $A[0]=4$.
• left child index $=2(1)+1=3$ → value $A[3]=5$.
• right child index $=2(1)+2=4$ → value $A[4]=1$. It has children (indices $3,4$ both $<n=5$), so index $1$ is internal.

$n=6$, last internal $=\lfloor 6/2\rfloor -1=2$. Process $i=2,1,0$.

Start: [2, 7, 4, 1, 9, 3].

i=2 (value $4$; left child index $=2(2)+1=5$ → value $A[5]=3$; right child index $=2(2)+2=6\ge n$, so none): $4\ge 3$ → no swap. [2,7,4,1,9,3]. i=1 (value $7$; left child index $=3$ → value $A[3]=1$, right child index $=4$ → value $A[4]=9$): largest is $9$ at index $4$ → swap. [2,9,4,1,7,3]. The demoted $7$ is now at index $4$, a leaf → stop. i=0 (value $2$; left child index $=1$ → value $A[1]=9$, right child index $=2$ → value $A[2]=4$): largest is $9$ → swap idx $0,1$. [9,2,4,1,7,3]. Follow the $2$ down: now at index $1$, left child index $=3$ → value $A[3]=1$, right child index $=4$ → value $A[4]=7$ → largest $7$ → swap idx $1,4$. [9,7,4,1,2,3]. The $2$ is at index $4$, a leaf → stop.

Result: [9, 7, 4, 1, 2, 3]. Verify heap property: $9\ge 7,4$ ✓; $7\ge 1,2$ ✓; $4\ge 3$ ✓.

$n=7$, last internal $=\lfloor 7/2\rfloor -1=2$. Process $i=2,1,0$. (Min-heap: parent $\le$ children.)

Start: [8, 3, 6, 1, 5, 9, 2].

i=2 (value $6$; left child index $=2(2)+1=5$ → value $A[5]=9$, right child index $=2(2)+2=6$ → value $A[6]=2$): smallest is $2$ → swap idx $2,6$. [8,3,2,1,5,9,6]. $6$ now at index $6$, a leaf → stop. i=1 (value $3$; left child index $=3$ → value $A[3]=1$, right child index $=4$ → value $A[4]=5$): smallest is $1$ → swap idx $1,3$. [8,1,2,3,5,9,6]. $3$ now at index $3$, a leaf → stop. i=0 (value $8$; left child index $=1$ → value $A[1]=1$, right child index $=2$ → value $A[2]=2$): smallest is $1$ → swap idx $0,1$. [1,8,2,3,5,9,6]. Follow the $8$: now index $1$, left child index $=3$ → value $A[3]=3$, right child index $=4$ → value $A[4]=5$ → smallest $3$ → swap idx $1,3$. [1,3,2,8,5,9,6]. $8$ now at index $3$, a leaf → stop.

Result: [1, 3, 2, 8, 5, 9, 6]. Verify: $1\le 3,2$ ✓; $3\le 8,5$ ✓; $2\le 9,6$ ✓.

$n=31$, $h=4$. Recall height is measured from the bottom, so $k=0$ are the leaves and $k=4$ is the single root. Exact counts (a perfect tree doubles each level going down):

Sum $=1+2+4+8+16=31$ ✓. Leaf bound at $k=0$: $\lceil 31/2^{0+1}\rceil =\lceil 31/2\rceil =\lceil 15.5\rceil =16$ ✓ — matches the exact leaf count. Notice the punchline visually: the two shortest heights ($0$ and $1$) already hold $16+8=24$ of the $31$ nodes — the numerous nodes are the cheap ones.

Multiply each height's node-count by its cost $k$: $T={\sum }_{k=0}^4(\text{nodes at }k)\cdot k=16\cdot 0+8\cdot 1+4\cdot 2+2\cdot 3+1\cdot 4.$ $T=0+8+8+6+4=26.$ Loose bound: $n\cdot h=31\cdot 4=124$. So the true work $26$ is under $1.4n$ (since $26/31\approx 0.84$), while the loose bound $124\approx 4n$ overcounts by nearly $5\times$. This is the gap between $O(n)$ (truth) and $O(n\log n)$ (loose bound) in a single concrete tree.

$S_4=\frac{0}{1}+\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\frac{4}{16}.$ $=0+0.5+0.5+0.375+0.25=\mathrm{1.625.}$ The infinite sum (parent note) is $2$. The remaining tail is only $2-1.625=0.375$, and it keeps shrinking. This is why heapify is linear: written carefully (with no Big-O misplaced inside the inequality), $T(n)\le \frac{n}{2}{\sum }_{k=0}^h\frac{k}{2^k}\le \frac{n}{2}{\sum }_{k=0}^{\infty }\frac{k}{2^k}=\frac{n}{2}\cdot 2=n=O(n).$ The multiplier is a constant (it converges to $2$), never a growing $\log n$.

Build max-heap. $n=3$, last internal $=\lfloor 3/2\rfloor -1=0$. Only $i=0$. i=0 (value $3$; left child index $=1$ → value $A[1]=1$, right child index $=2$ → value $A[2]=2$): $3\ge$ both → no swap. Heap: [3,1,2].

Extraction phase (swap root with last active element, shrink, sift root):

• Swap idx $0,2$: [2,1,3]; $3$ is now sorted-tail. Active size $=2$. Sift index $0$ (value $2$; left child index $=1$ → value $A[1]=1$): $2\ge 1$ → stop. [2,1 | 3].
• Swap idx $0,1$: [1,2,3]; active size $=1$. Nothing to sift. [1 | 2,3].
• One element left → done.

Sorted result (ascending): [1, 2, 3] ✓.

Build. $n=4$, last internal $=\lfloor 4/2\rfloor -1=1$. Process $i=1,0$.

• i=1 (value $2$; left child index $=3$ → value $A[3]=4$; right child index $=4\ge n$, none): $4>2$ → swap. [6,4,8,2].
• i=0 (value $6$; left child index $=1$ → value $A[1]=4$, right child index $=2$ → value $A[2]=8$): largest $8$ → swap idx $0,2$. [8,4,6,2]. $6$ at index $2$, leaf → stop. Heap after build: [8, 4, 6, 2]. Check: $8\ge 4,6$ ✓; $4\ge 2$ ✓.

extractMax. Return $8$. Move last element ($2$) to root, shrink to size $3$: [2,4,6]. Sift index $0$ (value $2$; left child index $=1$ → value $A[1]=4$, right child index $=2$ → value $A[2]=6$): largest $6$ → swap idx $0,2$. [6,4,2]. leaf → stop. Returned max $=8$; heap now [6, 4, 2] ✓ ($6\ge 4,2$).

Start from the geometric series (valid for $|x|<1$): ${\sum }_{k=0}^{\infty }{x}^k=\frac{1}{1-x}.$ Why differentiate? We want a $k$ to appear in front of each term (because our per-node cost is $k$). Differentiation w.r.t. $x$ pulls the exponent down as a coefficient — exactly the tool that manufactures a factor of $k$: $\frac{d}{dx}\sum x^k={\sum }_{k=1}^{\infty }k{x}^{k-1}=\frac{1}{(1-x{)}^2}.$ Multiply by $x$ to restore the exponent from $k-1$ to $k$: ${\sum }_{k=0}^{\infty }k{x}^k=\frac{x}{(1-x{)}^2}.$ At $x=\frac{1}{2}$: $\frac{1/2}{(1/2{)}^2}=\frac{1/2}{1/4}=2$.

Now the heapify bound — and where the $n/2$ comes from. Recall from the parent note that a (near-)complete tree has at most $n/2^{k+1}$ nodes at height $k$ (leaves are $\approx n/2$, height-1 nodes $\approx n/4$, and so on — each level up halves the count). A node at height $k$ costs at most $k$ sift-steps. So the total is the sum over heights of (count)$\times$(cost): $T(n)={\sum }_{k=0}^h\frac{n}{2^{k+1}}\cdot k=\frac{n}{2}{\sum }_{k=0}^h\frac{k}{2^k}.$ The factor $\frac{n}{2}$ is exactly the $\frac{1}{2^1}$ pulled out front from the node-count bound $\frac{n}{2^{k+1}}=\frac{n}{2}\cdot \frac{1}{2^k}$. Extending the finite sum to infinity only overestimates, so: $T(n)\le \frac{n}{2}{\sum }_{k=0}^{\infty }\frac{k}{2^k}=\frac{n}{2}\cdot 2=n=O(n).$ The step that kills the $\log$: replacing the finite sum ${\sum }_{k=0}^h$ by the infinite ${\sum }_{k=0}^{\infty }$ and observing it converges to the constant $2$. Because the series is bounded independent of $h$ (and hence of $n$), no $\log n$ factor survives.

Construction. Insert the values $1,2,3,\dots ,n$ in increasing order into a max-heap. Each newly inserted value is the largest so far, so it must bubble from a leaf all the way to the root. The $i$-th insertion sits in a heap of size $i$, whose height is $\lfloor {\log }_{2}i\rfloor$, and it climbs the full height: $T_{\text{insert}}={\sum }_{i=1}^n\lfloor {\log }_{2}i\rfloor =\Theta (n\log n).$ (The sum $\sum {\log }_{2}i={\log }_2(n!)=\Theta (n\log n)$ by Stirling.) Why bottom-up wins. siftUp moves the numerous leaves toward the root — the long, expensive direction. Bottom-up siftDown instead assigns the long journeys only to the rare tall nodes near the root, and the many leaves do zero work. The direction of travel, relative to where the crowd lives, is the whole difference.

The figure below draws a small tree. The many leaves are the red nodes at the bottom row (indices 3, 4, 5, 6); the root is the single white node at the top (index 0). Two arrows are overlaid: the red curved arrow labelled siftUp starts among the many red leaves and travels the entire height up to the root — that is the expensive path taken by every inserted leaf. The black arrow labelled siftDown starts at the lone root and heads downward — only that single rare node makes a long trip. Reading the picture in words: "expensive path × many nodes" gives $\Theta (n\log n)$; "long path × one node (plus cheaper trips for the few near the top)" gives $O(n)$.

Nodes at height $k$ in a perfect tree $=2^{h-k}$ (height $h$: $1$ node; height $0$: $2^h$ leaves). $T={\sum }_{k=0}^h{2}^{h-k}k=2^h{\sum }_{k=0}^h\frac{k}{2^k}.$ We first need the finite identity $\sum _{k=0}^h\frac{k}{2^k}=2-\frac{h+2}{2^h}$. Here is its derivation (a self-contained telescoping trick). Let $S={\sum }_{k=0}^h\frac{k}{2^k}$. Multiply by $\frac{1}{2}$ (this shifts every term one slot right): $\frac{1}{2}S={\sum }_{k=0}^h\frac{k}{2^{k+1}}={\sum }_{j=1}^{h+1}\frac{j-1}{2^j}.$ Subtract this from $S$ term-by-term (this is the same "$S-\frac{1}{2}S$" trick used to sum a geometric series, but here it leaves a clean geometric remainder): $S-\frac{1}{2}S={\sum }_{k=1}^h\frac{k-(k-1)}{2^k}-\frac{h}{2^{h+1}}={\sum }_{k=1}^h\frac{1}{2^k}-\frac{h}{2^{h+1}}.$ The remaining ${\sum }_{k=1}^h\frac{1}{2^k}=1-\frac{1}{2^h}$ is an ordinary geometric series. So: $\frac{1}{2}S=1-\frac{1}{2^h}-\frac{h}{2^{h+1}}⟹S=2-\frac{2}{2^h}-\frac{h}{2^h}=2-\frac{h+2}{2^h}.$ (Sanity check $h=4$: $2-\frac{6}{16}=2-0.375=1.625$, exactly matching Q7 ✓.) Now finish. Substitute this identity back: $T=2^h\left(2-\frac{h+2}{2^h}\right)=2^{h+1}-(h+2)=2^{h+1}-h-2.$ Since $n=2^{h+1}-1$, we get $T=n-(h+1)<n$. Heapify does fewer than $n$ sift-steps — even the hidden constant is below $1$. Spot check $h=4$ ($n=31$): $T=2^5-4-2=32-6=26$, matching Q6 exactly ✓.

• Start index $=\lfloor n/2\rfloor -1$, sift down, march up; for $n\le 1$ it is a no-op. ✓
• siftDown loops until leaf or property holds — never one swap. ✓
• Node at height $k$ (measured from the bottom, leaves $=0$) costs $k$; height-$k$ node count $\approx n/2^{k+1}$. ✓
• The magic constant: $\sum k/2^k=2$ → build is $O(n)$, in fact $<n$ steps. ✓
• Heapsort = $O(n)$ build $+$ $O(n\log n)$ extractions $=O(n\log n)$ total. ✓
• siftUp build = $O(n\log n)$; direction toward the crowded leaves is the enemy. ✓