A fast algorithm for optimum height-limited alphabetic binary trees

• Published in: SIAM journal on computing 1994-12, Vol.23 (6), p.1283-1312
• Main Authors: LARMORE, L. L, PRZYTYCKA, T. M
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Binary system; Codes; Computer science; Computer science; control theory; systems; Data processing. List processing. Character string processing; Exact sciences and technology; Leaves; Memory organisation. Data processing; Software
• ISSN: 0097-5397; 1095-7111
• DOI: 10.1137/s0097539792231167

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.