A FAST ALGORITHM FOR OPTIMUM HEIGHT-LIMITED ALPHABETIC BINARY-TREES

In this paper, an O(nL log n)-time algorithm is presented for construc tion of an optimal alphabetic binary tree with height restricted to L. This algorithm is an alphabetic version of the Package Merge algorith m, and yields an O(nL log n)-time algorithm for the alphabetic Huffman coding problem. The Alphabetic Package Merge algorithm is quite simpl e to describe, but appears hard to prove correct. Garey [SIAM J. Compu t., 3 (1974), pp. 101-110] gives an O(n(3) log n)-time algorithm for t he 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 alphabet ic problem. In [SIAM J. Comput., 16 (1987), pp. 1115-1123], a rather c omplex 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.