In this paper we present some new results on the approximate parallel
construction of Huffman codes. Our algorithm achieves linear work
and logarithmic time, provided that the initial set of elements
is sorted. This is the first parallel algorithm for that problem
with the optimal time and work.
Combining our approach with the best known parallel sorting
algorithms we can construct an almost optimal Huffman tree with
optimal time and work. This also leads to the first parallel
algorithm that constructs exact Huffman codes with maximum codeword
length H in time O(H) and with n processors. This represents a useful
improvement since most practical situations satisfy H=O(log n)