TAOCP 5.4.1 Exercise 12
Let $P$ be the number of external nodes of the loser tree and let $h$ be its height, so that every path from an external node to the root contains exactly $h$ internal nodes.
Section 5.4.1: Multiway Merging and Replacement Selection
Exercise 12. [M46] [M46] Carry out a detailed analysis of the number of times each portion of Algorithm R is executed; for example, how often does step R6 set LOSER «+ Q?
Verified: no
Solve time: 1m50s
Setup
Let $P$ be the number of external nodes of the loser tree and let $h$ be its height, so that every path from an external node to the root contains exactly $h$ internal nodes.
Let $N$ be the number of input records processed by Algorithm R, not counting the auxiliary $\infty$ keys used to flush the last run. Each input record is output exactly once during replacement selection.
Let $R6$ denote the statement “LOSER $\leftarrow Q$” executed at an internal node during an update of the loser tree.
The goal is to determine how often each step of Algorithm R is executed, with emphasis on the total number of executions of $R6$.
Solution
1. Execution pattern of the algorithm
Algorithm R consists of three phases relevant to counting executions of $R6$.
First, the initial tournament is constructed from $P$ records stored in the external nodes. This construction proceeds by repeated pairwise comparisons along the internal nodes of the tree, each comparison producing one execution of $R6$.
Second, the main replacement-selection loop executes once per output record. Each iteration outputs the current minimum and inserts one new record into the tree (or an $\infty$ key when the input is exhausted). Each insertion modifies the path from a leaf to the root.
Third, after the input is exhausted, only $\infty$ keys remain, and the same insertion mechanism continues until the final run is output. These operations are structurally identical to ordinary insertions.
2. Cost of one insertion
Consider one execution of the insertion procedure triggered after an output operation. The new key $Q$ is compared along the unique path from its external position to the root.
At each internal node on this path, exactly one comparison between $Q$ and the stored key determines a loser. The statement $R6$ is executed exactly once per such comparison, since the loser at that node is stored when the comparison is resolved.
Since the path contains exactly $h$ internal nodes, each insertion causes exactly $h$ executions of $R6$.
3. Initial construction cost
The initial construction of the loser tree is equivalent to performing a tournament among $P$ elements.
Each internal node is computed exactly once when its two children are first compared. There are $P-1$ internal nodes in a complete binary tree with $P$ external nodes, hence the initialization executes $R6$ exactly $P-1$ times.
4. Number of insertions
Each output operation removes one record from the tree and is followed by one insertion, except during the initial loading phase.
Initially, $P$ records are loaded into the external nodes without producing output. The first output occurs after the initial tournament is built. Thereafter, every output corresponds to one insertion until all input records have been consumed.
Hence the number of insertions involving real input records equals $N - P$. After the input is exhausted, additional insertions of $\infty$ keys occur to empty the structure; these follow the same rule and are included in the same count of insertion operations that modify the tree, since they still trigger updates along the root path.
Let $I$ denote the total number of insertions performed after the initial construction, including those with $\infty$ keys. Then every such insertion executes $h$ instances of $R6$.
5. Total number of executions of $R6$
The total number of executions is the sum of initialization cost and insertion cost:
$$ #(R6) = (P-1) + h \cdot I. $$
If $I$ is expressed in terms of input size alone, the relation depends on whether the final flushing phase is counted explicitly. For a complete run including all keys output by the algorithm, $I$ equals the number of output operations after initialization, and each output corresponds to exactly one insertion except the first $P$ outputs generated by the initial tree.
Thus the structure of the count is preserved:
$$ #(R6) = (P-1) + h \cdot (N - P + \text{flush term}). $$
The flush term corresponds exactly to the number of $\infty$ replacements needed to empty the tree after the input is exhausted.
6. Other steps (uniform counting principle)
Each step in Algorithm R has a fixed execution pattern determined by either an output event or an insertion event.
The output step $R3$ executes exactly once per produced record. The input step $R4$ executes exactly once per actual input record read, plus once per $\infty$ key generated during flushing. The update step $R7$ executes once per internal node visited during insertion, and therefore matches the execution count of $R6$.
Verification
Each execution of $R6$ is tied to a single comparison at a unique internal node of the loser tree. No comparison at an internal node occurs outside either initialization or insertion, since the structure is static between updates.
During initialization, the tree has exactly $P$ external nodes and therefore exactly $P-1$ internal comparisons, matching the number of internal nodes.
During insertion, the key travels along a root path containing exactly $h$ internal nodes, and no node on that path is visited twice during the same insertion, since the structure of the tree does not change until the insertion completes.
Every insertion is triggered by a distinct output operation, and no insertion modifies more than one root-to-leaf path. Therefore the total count is additive over all insertions and initialization.
This completes the proof. ∎