A work-efficient parallel algorithm for constructing Huffman codes
Ruy Luiz Milidiú, Eduardo Sany Laber, Artur Alves Pessoa · 1999
Given an alphabet /spl Sigma/={a/sub 1/,...,a/sub n/) and a corresponding list of weights [w/sub 1/,...,w/sub n/], a Huffman code for this alphabet is a prefix code that minimizes the weighted length of a code string, defined to be /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/, where l/sub i/ is the length of the code assigned to a/sub 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.