Huffman Encoding

Variable length encoding! How do we do it?

You gotta know when you're teminating! In this case, think of it kinda as start and stop bits. Make a tree, when you hit a left branch output a zero and you're done. Or, if you've hit the maximum depth of the tree, the 1 will also be an end bit.

To be more efficient, the most common characters want to be closer to the root of the tree!

Keep a minimum priority queue, sorting by frequency. Once you get the frequency, highest frequency is at the top!

Minimum in the queue is on the left, next least frequent is on the right, make a node. Add up frequency, put it as the root, put that in the queue again!

Then, you repeat. That way, if the two least likely together end up being more likely than another one, you've accounted for it.