Exercises — Heap sort — in-place, O(n log n)

Node index $i=2$.

• parent $=\lfloor (2-1)/2\rfloor =\lfloor 0.5\rfloor =0$ → value $9$.
• left $=2\cdot 2+1=5$ → value $2$.
• right $=2\cdot 2+2=6$ → value $1$.

So node $8$ sits under parent $9$, above children $2$ and $1$. What it looks like: the middle-of-second-row node in the figure above.

Check every parent against its children:

• idx0 ($9$): children idx1 $7$, idx2 $8$ → $9\ge 7$, $9\ge 8$ ✔
• idx1 ($7$): children idx3 $3$, idx4 $6$ → $7\ge 3$, $7\ge 6$ ✔
• idx2 ($8$): children idx5 $2$, idx6 $1$ → $8\ge 2$, $8\ge 1$ ✔
• idx3..6 are leaves (no children) → trivially valid.

Every parent dominates its children, so yes, it is a valid max-heap, and the max ($9$) is at index $0$. ✔

Last internal node $=\lfloor n/2\rfloor -1=\lfloor 7/2\rfloor -1=3-1=2$. Everything with index $>2$ has no children (since left$(3)=7\ge n$). So leaves are indices $3,4,5,6$, and build-heap starts sift-down at index $2$ and counts down to $0$.

Start at $i=0$ (val $2$). left $=1$ (val $8$), right $=2$ (val $5$).

• Largest of $\{2,8,5\}$ is $8$ at idx1 → swap idx0↔idx1: [8, 2, 5, 1, 4]. Follow down to $i=1$.
• At $i=1$ (val $2$): left $=3$ (val $1$), right $=4$ (val $4$). Largest is $4$ at idx4 → swap idx1↔idx4: [8, 4, 5, 1, 2]. Follow down to $i=4$.
• At $i=4$: left $=9\ge 5=n$, no children → stop.

Result: [8, 4, 5, 1, 2]. The value $2$ "sank" two levels. What it looks like: the small root traded places twice, each time with the larger of the two nodes beneath it.

Start index $=\lfloor 5/2\rfloor -1=1$. Sift-down $i=1$, then $i=0$.

• i=1 (val $10$): children idx3 $5$, idx4 $1$. $10$ already largest → no change. [4, 10, 3, 5, 1].
• i=0 (val $4$): children idx1 $10$, idx2 $3$. Largest $10$ → swap: [10, 4, 3, 5, 1]. Follow to $i=1$ (val $4$): children idx3 $5$, idx4 $1$. Largest $5$ → swap: [10, 5, 3, 4, 1]. Follow to $i=3$: leaf → stop.

Max-heap: [10, 5, 3, 4, 1], root $=10=\max$. ✔

Heap sort works by repeatedly swapping the root to the current back of the array. Whatever sits at the root gets parked last, then second-last, etc.

• A max-heap parks the biggest first (far end) → produces ascending.
• A min-heap parks the smallest first (far end) → the smallest ends up rightmost → produces descending.

So for descending order, use a min-heap. (See Priority Queue for the same root-access idea in a different context.)

Phase 1 (build). Start idx $=\lfloor 3/2\rfloor -1=0$.

• i=0 (val $3$): children idx1 $1$, idx2 $2$ → $3$ largest → no swap. Heap [3, 1, 2].

Phase 2 (extract), end runs $2,1$.

• end$=2$: swap idx0↔idx2 → [2, 1, |3]. sift_down(0, size $2$): child idx1 $1$ < $2$ → stop. [2, 1, |3].
• end$=1$: swap idx0↔idx1 → [1, |2, 3]. sift_down(0, size $1$): no children → stop.

Sorted: [1, 2, 3] ascending. ✔

Sift-down's precondition is: both subtrees of node $i$ are already valid heaps. We meet this by going bottom-up.

• Indices $\ge \lfloor n/2\rfloor$ are leaves — a lone element is already a valid heap, so sifting them is pointless work. Skipping them starts us at the last internal node $\lfloor n/2\rfloor -1$.
• Going downward to $0$ guarantees that when we sift node $i$, all deeper nodes (larger indices) have already been fixed, so their subtrees are valid heaps. Precondition satisfied.

If we started at the root ($i=0$) going up, the root's subtrees would still be raw/unsorted → precondition violated → sift-down could stop early on a bad comparison and leave the heap invalid.

The height a node can possibly sift is $O(\log n)$, but most nodes are near the bottom and can barely sift at all. Counting by height $h$ from the bottom: at height $h$ there are at most $\lceil n/2^{h+1}\rceil$ nodes, each costing $O(h)$: $T_{\text{build}}={\sum }_{h=0}^{\lfloor \log n\rfloor }\frac{n}{2^{h+1}}\cdot O(h)=O\left(n{\sum }_{h\ge 0}\frac{h}{2^h}\right).$ The series ${\sum }_{h\ge 0}h/2^h$ converges to $2$ (a constant), so the sum is $O(2n)=O(n)$. Phase 2 is different: there we always sift the root (full height each time) $n-1$ times → $O(n\log n)$. The two phases weight the heights differently, hence different totals.

Full sort wastes work — we only need $k$ elements out. Do:

1. Build a max-heap over the whole array in $O(n)$.
2. Extract only $k$ times (swap root to back, shrink, sift-down root). Each extraction is $O(\log n)$.

The last $k$ slots of the array now hold the $k$ largest in ascending order (reverse them if you want descending). Cost: $O(n)+k\cdot O(\log n)=O(n+k\log n).$ When $k\ll n$ this is essentially linear, far cheaper than the $O(n\log n)$ of a full sort. (This is exactly the Priority Queue use-case: repeated max access.)

Only the root was corrupted; both subtrees of the root are still valid heaps. That is precisely sift-down's precondition, so a single sift_down(A, 0, 7) suffices — no full rebuild needed.

• i=0 (val $3$): children idx1 $5$, idx2 $9$ → largest $9$ → swap: [9, 5, 3, 4, 1, 8, 2]. Follow to idx2 (val $3$).
• idx2: children idx5 $8$, idx6 $2$ → largest $8$ → swap: [9, 5, 8, 4, 1, 3, 2]. Follow to idx5 → leaf → stop.

Restored heap: [9, 5, 8, 4, 1, 3, 2] in $O(\log n)$, not $O(n)$. ✔

Consider extracting from a heap of size $n$ down to $n/2$. In each such extraction we swap the root to the back and sift a fresh element down. For the first $n/2$ extractions the heap still has size $\ge n/2$, so its height is $\lfloor {\log }_2(n/2)\rfloor =\lfloor {\log }_{2}n\rfloor -1\ge \frac{1}{2}{\log }_{2}n$ for $n\ge 4$. There exist heaps (e.g. build one where the sifted element must travel to a leaf every time — take distinct keys arranged so each new root is the global minimum of the remaining heap) where every one of these $n/2$ sift-downs traverses a full root-to-leaf path: $\text{work}\ge \frac{n}{2}\cdot \frac{1}{2}{\log }_{2}n=\frac{n{\log }_{2}n}{4}=\Omega (n\log n).$ Combined with the upper bound $O(n\log n)$, Phase 2 (and hence the whole sort, since build is only $O(n)$) is $\Theta (n\log n)$. Crucially this holds in the worst case too — heap sort has no bad-pivot blow-up like Quicksort, which is why Introsort switches to heap sort as its safety net.

Heap sort mutates the input array itself: the heap region and the growing sorted tail share one array, separated by the moving boundary end. No second array is allocated for data. The one choice that guarantees $O(1)$: writing sift-down as an iterative loop (as in the parent's code) instead of recursion. Recursion would push up to $O(\log n)$ stack frames — still small, but no longer strictly $O(1)$. The loop uses a fixed handful of index variables ($i,l,r,\text{largest}$) regardless of $n$. Contrast: Merge Sort must merge into a separate buffer of size $O(n)$, so it needs $O(n)$ extra space. Heap sort's array-as-tree trick (pure index arithmetic on a Complete Binary Tree, no pointers) is what buys the in-place property.