TAOCP 5.3.3 Exercise 17
We combine the algorithm of Exercise 16 (finding the maximum and minimum simultaneously) with the tree‑selection method of Kislitsyn’s theorem (formula (6) in the text).
Section 5.3.3: Minimum-Comparison Selection
Exercise 17. [20] (R. W. Floyd.) Show that it is possible to select, in order, both the $k$ largest and the $l$ smallest elements of a set of $n$ elements, using at most $\lceil \frac{3}{2}n \rceil - k - l + \sum_{n+1-k \le j \le n} \lceil \lg j \rceil + \sum_{n+1-l \le j \le n} \lceil \lg j \rceil$ comparisons.
Verified: no
Solve time: 15m12s
Solution
We combine the algorithm of Exercise 16 (finding the maximum and minimum simultaneously) with the tree‑selection method of Kislitsyn’s theorem (formula (6) in the text).
1. Build a double tournament tree.
Let (T) be an extended binary tree with (n) external nodes that is optimal for Kislitsyn’s bound; i.e., a tree for which
[
W_t(n) \le n - t + \sum_{n+1-t < j \le n} \lceil \lg j \rceil
]
holds for all (t). (Such a tree exists by the proof of Theorem S and formula (6).)
Using the divide‑and‑conquer procedure of Exercise 16, we build two tournament trees (T_{\text{max}}) and (T_{\text{min}}) both isomorphic to (T). At the leaf‑level comparisons we compare two elements; the larger becomes the winner for (T_{\text{max}}) and the smaller the winner for (T_{\text{min}}). At every higher internal node we compare the two max‑candidates (for (T_{\text{max}})) and the two min‑candidates (for (T_{\text{min}})).
A full tournament on (n) elements has (n-1) internal nodes. The two trees share the (\lfloor n/2 \rfloor) leaf‑level comparisons, so the total number of comparisons used is [ 2(n-1) - \lfloor n/2 \rfloor = \left\lceil \frac{3}{2}n \right\rceil - 2. ]
2. Extract the (k) largest elements.
The tree (T_{\text{max}}) already contains the outcome of every max‑comparison. By the tree‑selection method (Section 5.3.3) we repeatedly replace the current maximum with (-\infty) and sift up along its path to the root. The (i)th extraction (for (i=2,\dots,k)) requires a number of comparisons equal to the depth of the leaf of the (i)th largest element in (T). Kislitsyn’s theorem guarantees that the sum of the (k-1) largest leaf depths in the optimal tree (T) is at most
[
\sum_{n+1-k < j \le n} \lceil \lg j \rceil - (k-1).
]
Hence this phase uses at most that many additional comparisons.
3. Extract the (l) smallest elements.
Symmetrically, apply tree selection on (T_{\text{min}}) to obtain the second, third, …, (l)th smallest elements. The number of extra comparisons is at most
[
\sum_{n+1-l < j \le n} \lceil \lg j \rceil - (l-1).
]
4. Total comparisons.
Summing the three phases gives
[
\begin{aligned}
C &\le \left\lceil \frac{3}{2}n \right\rceil - 2
+ \sum_{n+1-k < j \le n} \lceil \lg j \rceil - (k-1)
+ \sum_{n+1-l < j \le n} \lceil \lg j \rceil - (l-1) \[4pt]
&= \left\lceil \frac{3}{2}n \right\rceil - k - l
+ \sum_{n+1-k < j \le n} \lceil \lg j \rceil
+ \sum_{n+1-l < j \le n} \lceil \lg j \rceil.
\end{aligned}
]
The bound stated in the exercise replaces the sums (\sum_{n+1-k < j \le n}) and (\sum_{n+1-l < j \le n}) by the slightly larger sums (\sum_{n+1-k \le j \le n}) and (\sum_{n+1-l \le j \le n}), which each include one additional nonnegative term (\lceil \lg(n+1-k)\rceil) and (\lceil \lg(n+1-l)\rceil) respectively. Therefore the total number of comparisons never exceeds
[
\left\lceil \frac{3}{2}n \right\rceil - k - l
- \sum_{n+1-k \le j \le n} \lceil \lg j \rceil
- \sum_{n+1-l \le j \le n} \lceil \lg j \rceil. ]
This completes the proof. ∎