Constructing Huffman Trees in Parallel
Lawrence L. Larmore, Teresa M. Przytycka · SIAM Journal on Computing · 1995
We present a parallel algorithm for the Huffman coding problem. We reduce the Huffman coding problem to the concave least weight subsequence (CLWS) problem and give a parallel algorithm that solves the latter problem in $O(\sqrt n \log n)$ time with n processors on a concurrent read exclusive write parameter random-access machine (CREW PRAM). This leads to the first sublinear-time $o(n^2 )$-total-work parallel algorithm for Huffman coding. This reduction of the Huffman coding problem to the CLWS problem also yields an alternative $O(n\log n)$-time (or linear-time, for a sorted input sequence) algorithm for Huffman coding.