Given a list of character and the frequencies they appear. Construct a Huffman Tree to encode all character.
For more details of building the
Huffman Tree and how to use it to encode and decode, please take a look at this article.
In terms of writing the code to build the
Huffman Tree, one solution I have is use a min heap to store
Node objects, each
Node object contains a character and its frequency, then every time poll the two lowest frequency
Node objects from the min heap and create the sum
Node, offer the sum
Node back to the min heap, repeat this process till we only have one
Node in the heap, and that will be the root node of the Huffman Tree. Eventually all the character nodes will become the leaves.
Encoding and decoding are pretty straightforward, just like how we traverse a tree to find a leaf with certain value, the only thing is we use
1 to indicate whether we are traversing left or right direction.
In terms of understanding the algorithm, this video really helped me - https://www.youtube.com/watch?v=K2gLEnwW2ps