3 ms·
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.
by mrkeen 2mo ago
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.
- inigyou 2mo agoHuffman 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.
- JohnKemeny 2mo agoYou 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.