July 4, 2001

In this paper we present new results on an approximate construction of Huffman trees. Our algorithms match asymptotically the time and work needed by known sorting algorithms. For example, we show that an almost-optimal Huffman tree can be constructed in O(log n) time with n processors on a CREW PRAM improving the O(log n log^* n) time and n processors result of Kirkpatrick and Przytycka. We also describe an O(n log log n) work algorithm that works on a CRCW PRAM with n/log n processors. This is the first parallel algorithm for the problem with time and work being nearly optimal.