TAOCP 5.2.3 Exercise 7
After 14 outputs, all but two elements have been replaced by $-\infty$ in the tournament structure of Fig.
Section 5.2.3: Sorting by Selection
Exercise 7. [**] [12] What will be the configuration of the tree in Fig. 23 after 14 of the original 16 items have been output?
Verified: yes
Solve time: 1m42s
After 14 outputs, all but two elements have been replaced by $-\infty$ in the tournament structure of Fig. 23, so only the two smallest original keys remain as finite values.
These two surviving keys occupy the two terminal positions in the tree that were never eliminated by a winning comparison against a later replacement by $-\infty$. Along the unique paths from these leaves to the root, every internal node has had all competing descendants replaced by $-\infty$, so each such node now simply propagates the remaining finite value upward.
Consequently, the configuration has collapsed to a single effective comparison between the two surviving keys: the root contains the larger of these two remaining keys (the second smallest of the original file), and its winning-child path contains that same value down to its leaf, while the other surviving key remains in the opposite leaf position as a subordinate branch value. Every other node in the complete binary tree contains $-\infty$, and no further comparisons among those nodes can affect the outcome. This completes the description of the configuration after 14 outputs. ∎