Construct Huffman Tree


  • 0
    T

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


  • 1

    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 0 and 1 to indicate whether we are traversing left or right direction.


  • 0
    A

    In terms of understanding the algorithm, this video really helped me - https://www.youtube.com/watch?v=K2gLEnwW2ps


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.