TAOCP 2.3.4.5 Exercise 13
Let the external nodes be numbered $m,m+1,\ldots,2m-1$, and let the internal nodes be numbered $m-1,m-2,\ldots,1$, so that the last internal node created is node $1$, the root.
Exercise 13. [**] [22] Design an algorithm that begins with $m$ weights $w_1\le w_2\le\cdots\le w_m$ and constructs an extended binary tree having minimum weighted path length. Represent the final tree in three arrays
$$ A[1]\ldots A[2m-1],\qquad L[1]\ldots L[m-1],\qquad R[1]\ldots R[m-1]; $$
here $L[i]$ and $R[i]$ point to the left and right children of internal node $i$, the root is node 1, and $A[i]$ is the weight of node $i$. The original weights should appear as the external node weights $A[m],\ldots,A[2m-1]$. Your algorithm should make fewer than $2m$ weight-comparisons. Caution: Some or all of the given weights may be negative!
Verified: yes
Solve time: 3m39s
Let the external nodes be numbered $m,m+1,\ldots,2m-1$, and let the internal nodes be numbered $m-1,m-2,\ldots,1$, so that the last internal node created is node $1$, the root.
Initialize
$$ A[m+j-1]\gets w_j,\qquad 1\le j\le m. $$
Maintain two queues:
$$ Q_1=(m,m+1,\ldots,2m-1), $$
whose elements are in nondecreasing order of weight, and
$$ Q_2=\emptyset. $$
For $i=m-1,m-2,\ldots,1$, perform two selections. At each selection, choose the node of minimum weight among the fronts of $Q_1$ and $Q_2$. If one queue is empty, take the front element of the other queue. Let the two selected nodes be $p$ and $q$. Then set
$$ L[i]\gets p,\qquad R[i]\gets q, $$
$$ A[i]\gets A[p]+A[q], $$
and append $i$ to the rear of $Q_2$.
After the final iteration, node $1$ is the root.
It remains to prove correctness and the comparison bound.
Correctness of the queue method
The usual argument for the two-queue implementation applies. Initially the weights in $Q_1$ are sorted. Every node inserted into $Q_2$ has weight equal to the sum of the two smallest available weights at the time of its creation. Hence the sequence of weights inserted into $Q_2$ is nondecreasing. Therefore both queues are always ordered by weight, and the smallest available node is always at the front of one of the queues. Thus each selection indeed extracts the minimum available weight.
Consequently the algorithm performs exactly the same sequence of merges as the Huffman procedure.
Optimality for arbitrary weights
The warning about negative weights must be addressed.
Let $T$ be any extended binary tree with leaf weights $w_1,\ldots,w_m$. If $d_j$ is the depth of the leaf carrying weight $w_j$, the weighted path length is
$$ P(T)=\sum_{j=1}^{m} w_j d_j . $$
For any constant $c$,
$$ P(T)+c\sum_{j=1}^{m} d_j =\sum_{j=1}^{m}(w_j+c)d_j . $$
Now every extended binary tree with $m$ external nodes has the same external path length:
$$ \sum_{j=1}^{m} d_j = I+2m-2, $$
by Eq. (3) of the text, where $I$ is the internal path length. Since an extended binary tree with $m$ leaves has exactly $m-1$ internal nodes, Eq. (3) gives
$$ \sum_{j=1}^{m} d_j =2(m-1), $$
which depends only on $m$, not on the shape of the tree.
Therefore
$$ \sum_{j=1}^{m}(w_j+c)d_j =P(T)+2(m-1)c . $$
The added term is independent of $T$. Hence a tree minimizes
$$ P(T)=\sum w_j d_j $$
if and only if it minimizes
$$ \sum (w_j+c)d_j . $$
Choose
$$ c\ge -w_1. $$
Then all shifted weights
$$ w_j' = w_j+c $$
are nonnegative.
Applying the standard Huffman theorem to the nonnegative weights $w_1',\ldots,w_m'$, the Huffman construction yields a tree $T_H$ minimizing
$$ \sum_{j=1}^{m} w_j' d_j . $$
Since minimizing the shifted objective is equivalent to minimizing the original objective, the same tree $T_H$ also minimizes
$$ \sum_{j=1}^{m} w_j d_j . $$
But the Huffman algorithm depends only on the ordering of the weights and on additions of weights. Replacing every weight by $w_j+c$ does not change the order, and the standard Huffman theorem guarantees that the merge sequence produced by the algorithm is optimal for the shifted instance. Therefore the tree produced by the above construction is an optimal extended binary tree for the original weights, even when some or all weights are negative.
Number of comparisons
There are $m-1$ merges, hence $2m-2$ selections.
A selection requires at most one weight comparison, namely a comparison of the front weights of $Q_1$ and $Q_2$ when both queues are nonempty. The very first selection requires no such comparison because $Q_2$ is initially empty.
Therefore the total number of weight comparisons is at most
$$ (2m-2)-1 = 2m-3 < 2m. $$
Thus the algorithm constructs the required arrays $A$, $L$, and $R$, produces an extended binary tree of minimum weighted path length for arbitrary real weights, and uses fewer than $2m$ weight comparisons.