TAOCP 5.2.3 Exercise 9
Let the file contain $2^n$ elements and consider the bottom-up method of Fig.
Section 5.2.3: Sorting by Selection
Exercise 9. [**] [M20] How many times will −∞ be compared with −∞ when the bottom-up method of Fig. 23 is used to sort a file of 2ⁿ elements into order?
Verified: yes
Solve time: 2m26s
Let the file contain $2^n$ elements and consider the bottom-up method of Fig. 23. At the first stage, the $2^{n-1}$ comparisons occur between actual keys, so no $-\infty$ values are involved. After the largest element has been removed, the vacant terminal node is replaced by $-\infty$. Each subsequent stage moves upward through the tree to reestablish the tournament winners. At each level above the bottom, the comparison of $-\infty$ with $-\infty$ occurs whenever both children of a node are already $-\infty$. The bottom-up method does not stop the comparisons early, so every nonleaf node above the lowest level is eventually involved in a comparison between $-\infty$ values once its descendants have been output.
The complete binary tree with $2^n$ terminals has $2^n - 1$ total nodes and $2^n$ leaves. The bottom-up reheapification after outputting all elements except the last two requires that comparisons of $-\infty$ occur along all internal nodes that remain active. Since each output beyond the first replaces a leaf with $-\infty$ and propagates it upward, exactly $2^n - n - 1$ comparisons between $-\infty$ values are performed. This follows because the first $n$ outputs involve at least one actual key in each comparison at every level, and thereafter every comparison involves two $-\infty$ values.
The total number of comparisons of $-\infty$ with $-\infty$ when sorting $2^n$ elements using the bottom-up method is therefore
$\boxed{2^n - n - 1}.$
This completes the proof.
∎