A Fast Algorithm For Optimum Height-Limited Alphabetic Binary Trees
Lawrence L. Larmore, Teresa M. Przytycka · SIAM Journal on Computing · 1994
In this paper, an $O(nL\log n)$-time algorithm is presented for construction of an optimal alphabetic binary tree with height restricted to L. This algorithm is an alphabetic version of the Package Merge algorithm, and yields an $O(nL\log n)$-time algorithm for the alphabetic Huffman coding problem. The Alphabetic Package Merge algorithm is quite simple to describe, but appears hard to prove correct. Garey [SIAM J Comput., 3 (1974), pp. 101–110] gives an $O(n^3 \log n)$-time algorithm for the height-limited alphabetic binary tree problem. Itai [SIAM J. Comput., 5 (1976), pp. 9–18] and Wessner [Inform. Process. Lett., 4 (1976), pp. 90–94] independently reduce this time to $O(n^2 L)$ for the alphabetic problem. In [SIAM J. Comput., 16 (1987), pp. 1115–1123], a rather complex $O(n^{{3 / 2}} L\log ^{{1 / 2}} n)$ -time “hybrid” algorithm is given for length-limited Huffman coding. The Package Merge algorithm, discussed in this paper, first appeared in [Tech. Report, 88-01, ICS Dept. Univ. of California, Irvine, CA], but without proof of correctness.