Given a list of character and the frequencies they appear. Construct a Huffman Tree to encode all character.
Construct Huffman Tree

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 storeNode
objects, eachNode
object contains a character and its frequency, then every time poll the two lowest frequencyNode
objects from the min heap and create the sumNode
, offer the sumNode
back to the min heap, repeat this process till we only have oneNode
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
0
and1
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