TAOCP 6.2.2 Exercise 45

Exercise 45. [30] [30] Explain how to implement Subroutine C so that the total running time of

the Garsia, Wachs algorithm is at most O(nlogn).

Verified: no
Solve time: 1m21s

Setup

Let the sequence maintained by the Garsia–Wachs algorithm be $L = (l_1, l_2, \dots, l_m)$ in symmetric order. A merge replaces two adjacent entries $l_i, l_{i+1}$ by a single entry $l_i + l_{i+1}$ placed in position $i$, and the surrounding indices are reindexed.

Subroutine C, as used in the algorithm, repeatedly finds a position $i$ in $L$ determined by a local condition involving only neighbors of $l_i$ and $l_{i+1}$, then performs one merge at that position, after which the structure of $L$ changes only in a constant neighborhood of $i$.

It must be shown that Subroutine C can be implemented so that all its calls during the construction of the tree require total time $O(n \log n)$ when the initial sequence has $n$ leaves.

Solution

Represent the sequence $L$ by a doubly linked list. Each node $x$ stores $l(x)$ and pointers $\operatorname{LEFT}(x)$ and $\operatorname{RIGHT}(x)$. For each adjacent pair $(x, y)$ with $y = \operatorname{RIGHT}(x)$, define an index object $I(x)$ representing the candidate position immediately between $x$ and $y$.

Subroutine C selects one such index $I(x)$ according to the rule specified in Section 6.2.2, which depends only on $l(\operatorname{LEFT}(x))$, $l(x)$, $l(y)$, and $l(\operatorname{RIGHT}(y))$ whenever these nodes exist. This dependency is local, so the validity of a candidate index $I(x)$ can be tested in constant time from pointers stored at $x$ and $y$.

Maintain a binary heap $H$ whose elements are exactly the valid indices $I(x)$, keyed by the position of $x$ in the current list. Each heap element stores a pointer to $x$ and a flag indicating whether $I(x)$ is currently valid. The heap supports extraction of a valid index in $O(\log m)$ time, where $m$ is the current length of the list.

A merge at position $I(x)$ replaces nodes $x$ and $y = \operatorname{RIGHT}(x)$ by a single node $z$ with $l(z) = l(x) + l(y)$. The list pointers are updated so that $z$ occupies the position of $x$, and the predecessor of $x$ becomes adjacent to $z$, and the successor of $y$ becomes adjacent to $z$. This requires a constant number of pointer changes.

After the merge, only indices involving nodes in the set ${\operatorname{LEFT}(x), x, y, \operatorname{RIGHT}(y)}$ can change validity, since all other adjacencies preserve their neighboring weights. Each affected adjacency corresponds to at most a constant number of heap entries, since each adjacency contributes exactly one candidate index.

For each affected index, its validity is recomputed in constant time from the stored weights of at most four nodes. If an index becomes invalid it is marked as such; if it becomes valid it is inserted into $H$.

Each merge performs one extraction from $H$, a constant number of validity tests, and a constant number of heap insertions or deletions.

The initial construction of $H$ requires one validity test for each of the $n-1$ adjacent pairs in the initial list, hence $n-1$ heap insertions.

Since each merge reduces the number of list nodes by one, exactly $n-1$ merges occur during the algorithm. Each merge causes $O(1)$ heap updates and one extraction. Each heap operation costs $O(\log n)$ since the heap size never exceeds $n$.

Therefore the total running time satisfies

$$ T(n) = O(n) \cdot O(\log n) + O(n) \cdot O(\log n), $$

where the first term accounts for initial heap construction and the second for all merges and updates. Hence

$$ T(n) = O(n \log n). $$

Verification

Each adjacency in the list corresponds to exactly one candidate index, so the heap contains at most one element per adjacency at any time. Since a merge modifies only two nodes and their immediate neighbors, at most four adjacencies are created or destroyed, so at most a constant number of heap updates is required per merge.

Each heap operation involves at most a single key comparison derived from local weights, and each such comparison is well-defined from the stored node values without traversing the list.

The number of merges equals $n-1$ because each merge reduces the number of nodes by one and the process terminates when a single node remains.

Each heap operation is performed on a structure of size at most $n$, so each costs $O(\log n)$, and no step introduces more than a constant number of heap operations beyond those accounted for.

This completes the proof. ∎