Not sure if this counts, but I learned Huffman coding the intuitive tree-based way. From memory it was O(nlogn), but you can just O(n) it in-place in an array.
Not sure if this counts, but I learned Huffman coding the intuitive tree-based way. From memory it was O(nlogn), but you can just O(n) it in-place in an array.
Huffman decoding you mean. All the fast decoders build tables processing N (8, 16, ...) bits at a time. If the next byte is 253 in state 6 that means output 15,28,28 and go to state 42...
There are probably even faster ways I don't know of.
You can't do it faster than O(n log n) for the simple reason that you need to sort the frequencies. If the symbols come sorted, then you can do it in O(n) time, yes, using two queues.