I recently went through the exercise of implementing a Huffman codec. Instead of the heap (or priority queue) I used the method that uses two queues to build the tree. See the second algorithm given here:
Even though I was writing it in Java, it was a lot of fun. I ended up with something that I could use on the server side, or compiled down to javascript in the client with GWT.
You still have to sort to build the queues. So you won't get below O(n log n) for the whole algorithm.
If you squint just about right, you can probably see the equivalence between sorting plus queues and the tree based techniques. Especially if you use a tree-structured sorting algorithm.
Indeed, though as the OP points out just below, if you have fixed frequencies, you don't have to sort.
That said, you generally have fixed frequencies with a predetermined set of constraints on the data, and you can determine the most common character frequency (or it's already known). I'm not sure how common this is in real-world applications of Huffman coding.
Seeing as you should only be building the tree once though, you're right--you'd be hard-pressed to tell the difference between the two approaches, barring implementation mistakes. Designing an implementation mistake that would cause noticeable differences is an exercise left to the reader.
In my particular case, the character frequencies are (more or less) fixed and the sorting could be done ahead-of-time before feeding the leaf nodes into the first queue. So I really did get O(n) at instantiation time. However, my n is so small that it didn't matter much.
Being able to relegate the cost of sorting to be a one-time cost on a server and allowing clients to build the tree they need for decoding in O(n) allows the client to [something about cake].
I guess I chose to build the tree on the client side because the list of character frequencies is a fairly compact representation of the encoding, and I didn't want to serialize the whole tree and send it across the wire to the client. Are you suggesting that the client doesn't need the tree at all? If so, how would the client do the decoding? I confess I'm doing the naive crawling down the tree to the left or right as a 0 or 1 is read. Is there some other way the client could be doing this?
Yes that's true, but they don't have equal cost to transmit over the wire. Why should I transmit the larger, more expensive tree when the character frequencies are a smaller representation of the same information?
I was explaining my tradeoff within the context of the GWT RPC object serialization. My tree is a graph with nodes of type BinaryTree<E>, where E in my case is a HuffmanNode object containing a char and an int. My alphabet has 66 characters plus an EOM character. The number of total nodes in the tree is 133. Although the extra internal nodes have HuffmanNode instances that do not contain a char, they do still contain the int sum of the frequencies of all the characters under that subtree. The BinaryTree class itself has left, right, and parent references. So the way the GWT serialization format works out for this beast ends up being larger than the characters and frequencies alone.
I know what you're thinking: why not transform the tree into an Ahnentafel list and marshall it to a string containing only the alphabet characters in the appropriate slots, and use another chosen character to represent null slots, and write another implementation of the decoder that's driven off of the array? (Edit: Or, better still, transform it to a canonical Huffman codebook)
Yes, of course I could do that — and I actually want to. Alas, I have bigger fish to fry than writing the tree transformation code, the marshaling code, and the additional decoder implementation. So, when it's all said & done, according to the tradeoffs I was willing to make, my clients get to build the tree in O(n). I can tell that you're vexed that it worked out that way, but that's life.
http://en.wikipedia.org/wiki/Huffman_coding#Basic_technique
Even though I was writing it in Java, it was a lot of fun. I ended up with something that I could use on the server side, or compiled down to javascript in the client with GWT.