CONSTRUCTING HUFFMAN TREES IN PARALLEL

We present a parallel algorithm for the Huffman coding problem. We red uce the Huffman coding problem to the concave least weight subsequence (CLWS) problem and give a parallel algorithm that solves the latter p roblem in O(root n log n) time with n processors on a concurrent read exclusive write parameter random-access machine (CREW PRAM). This lead s to the first sublinear-time o(n(2))-total-work parallel algorithm fo r Huffman coding. This reduction of the Huffman coding problem to the CLWS problem also yields an alternative O(n log n)-time (or linear-tim e, for a sorted input sequence) algorithm for Huffman coding.