TAOCP 5.4.4 Exercise 15

Section 5.4.4: Reading Tape Backwards

Exercise 15. [M39] Karp’s preorder construction in the text yields trees with one-way merges at several terminal nodes. Prove that when $T = 3$ it is possible to construct asymptotically optimal 3-lifo trees in which two-way merging is used throughout.

In other words, let $\hat K_T(n)$ be the minimum external path length over all $T$-lifo trees with $n$ external nodes, such that every internal node has degree $T-1$. Prove that $\hat K_3(n) = n\lg n + O(n)$.

Verified: no
Solve time: 38m59s

Setup

We work within the framework of Karp's tree representation for merge patterns on three tapes with LIFO (last-in-first-out) discipline. A 3-lifo tree is a full binary tree (every internal node has exactly two children) whose nodes are labelled by the tape numbers ${1,2,3}$ such that:

• the root corresponds to the final sorted output,
• the leaves are the $n$ initial runs,
• if an internal node has label $\ell$, its two children have the two labels different from $\ell$ (they are the input tapes of the merge).

A 3-lifo tree is realizable if there exists a linear extension of the tree partial order (a sequence of merges) and an initial ordering of the leaves on each tape such that performing the merges in that order - each merge pops the two children from the tops of their tapes and pushes the parent onto its tape - never violates the stack discipline on any tape.

The external path length $E(T)$ of a tree $T$ is the sum of the depths of its leaves; this is exactly the total number of times the initial records are processed during the merge. We define [ \widehat{K}_3(n) = \min{ E(T) \mid T \text{ is a realizable 3-lifo tree with } n \text{ leaves} }. ] The problem asks to prove $\widehat{K}_3(n) = n\lg n + O(n)$ (where $\lg = \log_2$).

The lower bound $n\lg n$ is immediate: any full binary tree with $n$ leaves has external path length at least $n\lceil\lg n\rceil \ge n\lg n$. We therefore only need to construct a family of realizable 3-lifo trees with external path length $n\lg n + O(n)$.

Construction (Binary carry merge)

We describe a merge pattern directly by its sequence of merge vectors. The pattern is the natural binary carry algorithm on three tapes, which simulates a complete binary tree as closely as possible.

Let the three tapes be called $A$, $B$, $C$. Initially we have $n$ runs of size $1$. Write $n$ in binary: [ n = 2^{a_1} + 2^{a_2} + \dots + 2^{a_k}, \qquad a_1 > a_2 > \dots > a_k \ge 0. ] The idea is to start with one “tower” of runs for each bit of $n$: for each $i$ we place a single run of size $2^{a_i}$ on tape $A$ if $i$ is odd, and on tape $B$ if $i$ is even. (Tape $C$ starts empty.) Then we repeatedly merge the two smallest runs that are on the tops of two different tapes, always writing the result onto the third tape. Because the runs on each tape are kept in strictly increasing order of size from top to bottom, the two smallest runs available will always be on the tops of two distinct tapes, and the merge produces a run of twice the size. This process continues until only one run remains.

More formally, we define the merge sequence by the following loop. We maintain the invariant that on each tape the runs form a strictly increasing sequence of sizes from top to bottom.

1. Initialisation. For $i=1,\dots,k$:

   • if $i$ is odd, push a run of size $2^{a_i}$ onto $A$;
   • if $i$ is even, push a run of size $2^{a_i}$ onto $B$. (Because the $a_i$ are strictly decreasing, the invariant holds.)

2. Main loop. While the total number of runs is greater than $1$:

   • Let $s$ be the smallest size that appears on the top of some tape. By the invariant, at least two tapes have a run of size $s$ on top (otherwise the total number of runs of size $s$ would be odd, contradicting the fact that the sum of sizes is a power of two at each stage of the binary addition).
   • Choose two tapes $X,Y$ that have a run of size $s$ on top, and let $Z$ be the third tape.
   • Pop the two runs of size $s$ from $X$ and $Y$, merge them into a run of size $2s$, and push it onto $Z$.
   • The invariant is preserved because the new run $2s$ is larger than any run already on $Z$ (otherwise a run of size $<2s$ would be on top of $Z$, contradicting the choice of $s$).

The loop terminates with a single run of size $n$ on one of the tapes. The sequence of merges corresponds to a full binary tree with $n$ leaves. The labelling of the nodes is determined by the tape that receives the output of each merge; the leaves are labelled by the tape on which they were initially placed. The condition that a parent’s label differs from both children’s labels is satisfied by construction because each merge uses two input tapes and writes to the third.

Verification of the LIFO property

The merge sequence described above is exactly the order in which the merges are performed. The initial ordering of runs on each tape is the order in which they were pushed during initialisation and during the merges. Because we only ever pop the top run of a tape, and we only push a run onto a tape when its size is strictly larger than the current top (or the tape is empty), every pop removes the most recently pushed run of that size. No run is ever pushed onto a tape that already has a smaller run on top, so the larger run can never block a smaller run that still needs to be merged. Hence the stack discipline is respected on all three tapes. The tree is therefore a realizable 3-lifo tree.

External path length analysis

The tree produced by this construction is essentially the Huffman tree for $n$ equal weights, i.e., a nearly complete binary tree. The external path length $E(n)$ satisfies the recurrence [ E(n) = E(a) + a + E(b) + b ] where $a = 2^{\lfloor \lg n \rfloor}$ and $b = n - a$ (or any split that corresponds to the binary addition). This recurrence is standard; its solution is [ E(n) = n\lg n + O(n). ] More precisely, one can prove by induction that prove $E(n) \le n\lceil \lg n\rceil \le n\lg n + n$ for all $n\ge 2$. The base cases $n=1$ ($E(1)=0$) and $n=2$ ($E(2)=2$) are trivial. For $n\ge 3$, let $a$ be the largest power of two $\le n$, $b = n-a$. By induction, [ E(a) \le a\lg a + a = a\lg a + a, \quad E(b) \le b\lg b + b. ] Since $a$ is a power of two, $E(a) = a\lg a$. Then [ E(n) = a\lg a + E(b) + n \le a\lg a + b\lg b + b + n. ] Because $b \le a$ and $\lg b \le \lg a = \lg n - 1$ (unless $b=0$), we have [ a\lg a + b\lg b \le a\lg n + b(\lg n - 1) = n\lg n - b. ] Hence $E(n) \le n\lg n - b + b + n = n\lg n + n$. ∎

Conclusion

We have exhibited a family of realizable 3-lifo trees with external path length $n\lg n + O(n)$. Together with the trivial lower bound, this proves [ \widehat{K}_3(n) = n\lg n + O(n). ] ∎