A work-efficient parallel algorithm for constructing Huffman codes

Given an alphabet Σ={a₁,...,a_n) and a corresponding list of weights [w₁,...,w_n], a Huffman code for this alphabet is a prefix code that minimizes the weighted length of a code string, defined to be Σ_i=1 ⁿw_il_i, where l_i is the length of the code assigned to a_i. We present ES-ParHuff, a work-efficient PRAM CREW algorithm for constructing Huffman codes. An important feature of the algorithm is its simplicity. This algorithm is a direct parallelization of Huffman´s algorithm. ES-ParHuff runs in O(Hloglog(n/H)) time with O(n) work, where H is the length of the longest generated code