TAOCP 5.4.9 Exercise 7
Let each initial run $i$ have weight $w_i$.
Section 5.4.9: Disks and Drums
Exercise 7. [M24] [M24] When the initial runs are not all the same length, the best merge pattern (in the sense of Theorem H) minimizes aD(7) + GE(7), where D(T) and E(T) now represent weighted path lengths: Weights w1,...,Wn (corresponding to the lengths of the initial runs) are attached to each leaf of the tree, and the degree sums and path lengths are multiplied by the appropriate weights. For example, if 7 is the tree of Fig. 92, we would have D(T) = 6wi + 6w2 + 7w3 + 9wa + 9ws + Two + 4w7 + 4:8, E(T) = 2wi + 2w2 + 2wzs + 3w4a + 3ws5 + 2we + w7 + ws.
Prove that there is always an optimal pattern in which the shortest k runs are merged first, for some k.
Verified: no
Solve time: 4m19s
Let each initial run $i$ have weight $w_i$. For a merge pattern $T$, let $d_i(T)$ and $e_i(T)$ be the contributions of run $i$ to $D(T)$ and $E(T)$. The objective is
$$ aD(T) + gE(T) = \sum_{i=1}^n w_i\bigl(a,d_i(T) + g,e_i(T)\bigr). $$
Define the position cost
$$ c_i(T) := a,d_i(T) + g,e_i(T), $$
so the objective becomes
$$ \sum_{i=1}^n w_i c_i(T). $$
Thus we are assigning weights $w_i$ to the leaves of a fixed full binary merge tree, where each leaf position $i$ has cost $c_i(T)$. The costs depend only on the structure of $T$, not on the labels.
1. Reformulation as weighted external path optimization
For a fixed tree shape $T$, the optimal labeling of leaves by weights minimizes $\sum w_i c_i(T)$. By the rearrangement inequality, this is minimized by assigning larger weights to smaller costs. Hence, in any optimal labeled tree, weights are nondecreasing along nonincreasing costs:
$$ w_i \le w_j \implies c_i(T) \ge c_j(T). $$
In particular, the smallest weights must be assigned to leaves of largest cost.
2. Structure of maximum-cost leaves
Let $S$ be the set of leaves maximizing $c_i(T)$. We first justify a structural fact about full binary trees.
Lemma 1. In any full binary tree, every leaf of maximum depth belongs to a sibling pair of leaves of the same depth.
Proof. In a full binary tree every internal node has exactly two children. Let $v$ be a leaf of maximum depth. Its parent exists and has two children at the same depth as $v$. Since $v$ is a leaf, its sibling must also be a leaf (otherwise the tree could not be full at that parent). Hence leaves of maximum depth occur in sibling pairs. ∎
Since $c_i(T)$ is strictly increasing with depth in both $d_i$ and $e_i$, leaves of maximum $c_i(T)$ occur among leaves of maximum depth, hence also form sibling pairs.
Thus the set $S$ of maximum-cost leaves can be partitioned into sibling pairs.
3. Placing the smallest weights at deepest positions
Let $S$ be the set of maximum-cost leaves. We now show that in some optimal labeling, the smallest weights occupy $S$.
Suppose not. Then there exist leaves $i \in S$ and $j \notin S$ such that $w_i > w_j$ but $c_i(T) \ge c_j(T)$. Swapping the labels of $i$ and $j$ changes the objective by
$$ \Delta = (w_i - w_j)(c_j(T) - c_i(T)) \le 0, $$
with strict improvement if $c_i(T) > c_j(T)$. Hence in an optimal tree no such inversion can occur.
Therefore the smallest $|S|$ weights can be assigned to the maximum-cost leaves, i.e., to the deepest sibling pairs.
Let $k$ be the number of leaves in $S$. Then the $k$ smallest weights occupy exactly the deepest level of the tree, grouped into sibling pairs.
4. Existence of a smallest-weight sibling pair
Since the $k$ smallest weights occupy the deepest level, at least one sibling pair at maximum depth consists of two among the smallest remaining weights. In particular, the two globally smallest weights $w_1, w_2$ can be assumed (by relabeling within $S$) to form a sibling pair at maximum depth.
Thus there exists an optimal tree in which $w_1$ and $w_2$ are siblings.
5. Optimal substructure under contraction
Let $T$ be such an optimal tree in which $w_1$ and $w_2$ are siblings. Replace these two leaves by a single leaf of weight $w' = w_1 + w_2$, obtaining a reduced instance $T'$ with $n-1$ weights.
The key point is that all paths above the merged sibling pair are unchanged except for an additive constant contribution:
$$ w_1 c + w_2 c = (w_1 + w_2)c, $$
so the contribution of the pair depends only on their parent position. Hence any improvement in the reduced tree would lift to an improvement in the original tree, contradicting optimality.
Therefore $T'$ is optimal for the reduced instance.
6. Induction and greedy merging
By applying the same argument to $T'$, we obtain that in an optimal solution for $n-1$ weights, the two smallest remaining weights can be merged first. Iterating, we obtain a sequence of optimal contractions in which at each step the two smallest available runs are merged.
Thus there exists an optimal merge pattern generated by the greedy rule:
$$ \text{repeatedly merge the two smallest runs.} $$
7. Conclusion
In the greedy construction, after $k-1$ merges, exactly the $k$ smallest initial runs have been involved in merges forming the bottom portion of the tree. Equivalently, the construction begins with merges among the shortest runs only.
Hence there exists an optimal merge pattern in which the shortest $k$ runs are merged first for some $k$.