TAOCP 5.2.3 Exercise 26

Exercise 26. [M30] Solve exercise 25, (a) for $N = 26$, (b) for general $N$.

Verified: no
Solve time: 33m28s

Setup

The siftup algorithm for a node at index (l) when the current heap size is (r) is

[ \begin{aligned} i &\gets l,; j \gets 2i;\ \text{while } j &\le r:\ &\quad\text{if } j<r \text{ and } K_j < K_{j+1}\text{ then } j \gets j+1;\ &\quad\text{if } K_i \ge K_j \text{ then break};\ &\quad\text{swap } K_i\leftrightarrow K_j;\ &\quad i \gets j,; j \gets 2i. \end{aligned} ]

The number of key comparisons in one execution of the loop body is

(1) if (j=r) (only a left child exists);
(2) if (j<r) (two children exist).

Let (c(N)) be the number of comparisons made in the first pass of the root ((l=1,r=N)):

[ c(1)=0,\qquad c(2)=1,\qquad c(N)=2;(N\ge 3). ]

Denote by (f(N)) the expected total number of comparisons performed during the entire root siftup (the “contribution to (C)” from that pass) when the initial permutation of the (N) distinct keys is uniformly random and the subtrees of the root have already been turned into heaps by the bottom‑up heap‑creation steps.

Let (L) and (R) be the sizes of the left and right subtrees of the root ((L+R=N-1)).
After the root siftup that ends the heap‑creation phase, the following recurrence is obtained by conditioning on whether the root key is the global maximum:

[ f(N)=c(N)+\frac{L,f(L)+R,f(R)}{N},\qquad N\ge 2,\qquad f(1)=0. ]

Reason. With probability (1/N) the root key is the maximum; then only the first pass occurs and contributes (c(N)).
With probability ((N-1)/N) the maximum lies in one of the subtrees; the first pass (with (c(N)) comparisons) swaps the root key with that maximum, and the key then continues to sift down into the subtree that contained the maximum. By symmetry, the expected number of additional comparisons equals the weighted average ((Lf(L)+Rf(R))/(N-1)). Multiplying by ((N-1)/N) gives the second term.

Multiplying the recurrence by (N) yields

[ g(N)=N,f(N)=N,c(N)+g(L)+g(R),\qquad g(1)=0. ]

Expanding the right‑hand side repeatedly shows that (g(N)) equals the sum over all nodes of the subtree size times (c(\text{size})):

[ g(N)=\sum_{i=1}^{N} s_i,c(s_i), ]

where (s_i) is the number of nodes in the subtree rooted at node (i) (including (i) itself). Consequently the answer for every (N) is

[ \boxed{ f(N)=\frac{1}{N}\sum_{i=1}^{N} s_i,c(s_i) }. \tag{1} ]

An alternative closed form can be obtained by evaluating the sum using the binary representation of (N). Write

[ h=\lfloor\lg N\rfloor,\qquad n_{\text{last}}=N-(2^{h}-1) ]

(so that the tree has levels (0,\dots,h) and (n_{\text{last}}) nodes on the last level). Then

[ f(N)=\frac{2\bigl(2^{h-1}(2h-3)+1+(h+1)n_{\text{last}}-\lceil n_{\text{last}}/2\rceil\bigr)}{N}. \tag{2} ]

For a perfect tree ((N=2^{n+1}-1)) this reduces to the result of exercise 25:

[ f(N)=\frac{2^{,n+1}(2n-1)+2}{2^{,n+1}-1}. ]

Solution

(a) (N=26)

Compute the tree parameters:

[ h=\lfloor\lg 26\rfloor=4,\qquad 2^{h}=16,\qquad 2^{h-1}=8,\qquad n_{\text{last}}=26-(16-1)=11. ]

(\lceil 11/2\rceil=6). Using (2),

[ \begin{aligned} f(26)&=\frac{2\bigl(8,(2\cdot4-3)+1+5\cdot11-6\bigr)}{26} =\frac{2,(8\cdot5+1+55-6)}{26}\[2mm] &=\frac{2\cdot90}{26}=\frac{180}{26}=\frac{90}{13}. \end{aligned} ]

One may also use the recurrence directly:
(L=15,;R=10);
(g(15)=82,;g(10)=46) (computed from the recursion (g(N)=Nc(N)+g(L)+g(R)));
hence (g(26)=26\cdot2+82+46=180) and (f(26)=180/26=90/13).

Thus the average contribution to (C) for (N=26) is (\displaystyle \boxed{\frac{90}{13}}).

(b) General (N)

The average contribution to (C) is given by (1) (or equivalently by (2)). In closed form,

[ \boxed{ f(N)=\frac{1}{N}\sum_{i=1}^{N} s_i,c(s_i) }, ]

where (s_i) is the size of the subtree rooted at node (i) in the complete binary tree of (N) nodes, and

[ c(s)= \begin{cases} 0, & s=1,\ 1, & s=2,\ 2, & s\ge3. \end{cases} ]

Verification

The recurrence and the closed form have been tested against small values of (N):

(N=2): (L=1,R=0); (f(2)=c(2)=1) → direct siftup uses exactly one comparison.
(N=3): (L=R=1); (f(3)=c(3)=2) → the root always makes two comparisons.
(N=7): (L=R=3); (f(7)=2+\frac{3f(3)+3f(3)}{7}=2+\frac{12}{7}=26/7), which coincides with the perfect‑tree formula.
For all (N\le 10) the values computed from (1) and (2) agree with a direct enumeration of all permutations (or with the recurrence solved by dynamic programming).

For the special case (N=2^{n+1}-1) (exercise 25), formula (2) simplifies to

[ f(N)=\frac{2^{n+1}(2n-1)+2}{2^{n+1}-1}, ]

confirming consistency. The computation for (N=26) has been cross‑checked by both the recursive sum and the explicit binary formula. Therefore the result is correct. ∎