TAOCP 5.2.3 Exercise 23
We consider the heap creation phase of Algorithm H (heapsort) as described in Section 5.
Section 5.2.3: Sorting by Selection
Exercise 23. [M28] (a) Prove that the length of scan, $B$, in a siftup algorithm never exceeds $\lfloor \lg(r/l) \rfloor$. (b) According to (8), $B$ can never exceed $N \lfloor \lg N \rfloor$ in any particular application of Algorithm H. Find the maximum value of $B$ as a function of $N$, taken over all possible input files. (You must prove that an input file exists such that $B$ achieves this maximum value.)
Verified: no
Solve time: 18m29s
Setup
We consider the heap creation phase of Algorithm H (heapsort) as described in Section 5.2.3. The input is a permutation of (N) distinct keys stored in an array (K[1\ldots N]). The heap creation phase builds a max‑heap by repeated siftup insertions:
[ \text{for } r = 2 \text{ to } N:\quad \text{sift up } K[r] \text{ into the heap } K[1\ldots r-1]. ]
A single siftup operation starts with the element at index (r) and repeatedly compares it with its parent at (\lfloor k/2\rfloor); if it is larger, the two are swapped and the process continues with the parent index. The length of scan is the number of comparisons (equivalently, the number of promotions) performed during this siftup.
Part (a) states a general lemma: when a siftup is performed on a subarray (K[l\ldots r]) that already satisfies the heap property except possibly at (r), the scan length never exceeds (\lfloor \lg(r/l)\rfloor).
Part (b) concerns the total scan length (B) over the whole heap creation phase. Equation (8) in the text gives the coarse bound (B \le N\lfloor\lg N\rfloor). We are to find the exact maximum of (B) over all input permutations and prove it is attainable.
Solution
(a) Bound for a single siftup
Let the heap occupy indices (l, l+1, \ldots, r) with the heap property holding everywhere except possibly at (r). The siftup moves the element initially at (r) upward by repeatedly replacing the current index (k) with its parent (\lfloor k/2\rfloor). After (t) steps the index becomes (\lfloor r/2^t\rfloor). The process can continue only while this index is (\ge l). Hence the maximum possible number of steps (B) satisfies
[ \left\lfloor \frac{r}{2^B} \right\rfloor \ge l \quad\Longrightarrow\quad \frac{r}{2^B} \ge l \quad\Longrightarrow\quad 2^B \le \frac{r}{l} \quad\Longrightarrow\quad B \le \lfloor \lg(r/l)\rfloor. ]
This completes the proof of (a). ∎
(b) Maximum total scan length in Algorithm H
In Algorithm H the heap creation phase always uses (l = 1) and performs a siftup for each (r = 2, 3, \ldots, N). By part (a) the scan length for the (r)-th insertion is at most (\lfloor\lg r\rfloor). Therefore the total scan length (B) satisfies
[ B \le \sum_{r=2}^{N} \lfloor\lg r\rfloor. ]
Equation (8) in the text relaxes this to (B \le N\lfloor\lg N\rfloor) because (\lfloor\lg r\rfloor \le \lfloor\lg N\rfloor) for all (r\le N).
The upper bound (\sum_{r=2}^{N}\lfloor\lg r\rfloor) is achievable. Take the input permutation in strictly increasing order (e.g., (1,2,\ldots,N)). When the (r)-th element is inserted, it is larger than every element already in the heap (which are exactly (1,\ldots,r-1)). Consequently it sifts up all the way to the root, performing exactly the maximum possible number of steps. For a complete binary tree stored in an array, the number of ancestors of node (r) is (\lfloor\lg r\rfloor). Hence the scan length for the (r)-th insertion equals (\lfloor\lg r\rfloor), and the total (B) attains the sum.
It remains to express this sum in closed form. Let (m = \lfloor\lg N\rfloor). For each (j = 0,1,\ldots,m-1) there are exactly (2^j) integers (r) with (\lfloor\lg r\rfloor = j) (namely (r = 2^j, \ldots, 2^{j+1}-1)). For (j = m) there are (N - 2^m + 1) such integers ((r = 2^m, \ldots, N)). Thus
[ \begin{aligned} B_{\max} &= \sum_{j=0}^{m-1} j\cdot 2^j ;+; m,(N - 2^m + 1). \end{aligned} ]
Using the identity (\sum_{j=0}^{m-1} j,2^j = (m-2)2^m + 2) (easily proved by induction or by differentiating the geometric series), we obtain
[ \begin{aligned} B_{\max} &= (m-2)2^m + 2 + mN - m2^m + m \ &= mN - 2^{m+1} + m + 2. \end{aligned} ]
Since (m = \lfloor\lg N\rfloor), the maximum value of (B) as a function of (N) is
[ \boxed{B_{\max} = N\lfloor\lg N\rfloor - 2^{\lfloor\lg N\rfloor+1} + \lfloor\lg N\rfloor + 2}. ]
The increasing permutation (1,2,\ldots,N) (or any strictly increasing sequence of distinct keys) achieves this maximum, which completes the proof. ∎
Verification
We verify the formula and the attainability for small (N) by direct enumeration.
| (N) | (m=\lfloor\lg N\rfloor) | Formula (mN - 2^{m+1}+m+2) | Sum (\sum_{r=2}^N\lfloor\lg r\rfloor) | Achieved by increasing order? |
|---|---|---|---|---|
| 1 | 0 | (0 - 2 + 0 + 2 = 0) | (empty sum = 0) | vacuously yes |
| 2 | 1 | (2 - 4 + 1 + 2 = 1) | (\lfloor\lg 2\rfloor = 1) | yes (1,2) |
| 3 | 1 | (3 - 4 + 1 + 2 = 2) | (1+1=2) | yes (1,2,3) |
| 4 | 2 | (8 - 8 + 2 + 2 = 4) | (1+1+2=4) | yes (1,2,3,4) |
| 5 | 2 | (10 - 8 + 2 + 2 = 6) | (1+1+2+2=6) | yes (1,2,3,4,5) |
| 6 | 2 | (12 - 8 + 2 + 2 = 8) | (1+1+2+2+2=8) | yes (1,2,3,4,5,6) |
All values match. The increasing permutation always yields the maximum because each new element is larger than all previous ones, forcing the maximum possible number of promotions at every step. No permutation can exceed the sum of the individual maxima, so the formula is correct.