Data Agencies - Huffman Trees

What is a Huffman tree?

Let's first look at the definition of Huffman tree:
Huffman tree (Huffman Tree) is in the case of leaf nodes and weights determined,The binary tree with the smallest weighted path length is also called the optimal binary tree.

When I saw this definition, I was stunned. What leaf nodes and weights are good, so what does the path mean, the way from one node to another?And what does the weighted path length mean?

What is a path?

In a tree, all the nodes passed from one node to another are called paths between two nodes.

In the above binary tree, from root node A toThe path of leaf node H is A, B, D, H.
So the path length is 3, which is A=>B=>D=>H.

What is the weighted path length of a node?

The weighted path length of the nodeRefers to: the product of the weight of the node * the path length from the root node of the tree to the node.
That is 1x3=3.

Then the weighted path length of the tree is: the sum of the weighted path lengths of all leaf nodes
that is 1x3+2x3+3x2+4x2+5x2=33

Huffman tree construction

Assuming there are 5 leaf nodes and the weights are 1, 2, 3, 4, and 5 in order, how to construct a Huffman tree, that is, the tree with the smallest weighted path length?

Pseudo code implementation:
See the above mentioned every timeWhen the two nodes with the smallest value are merged, is it possible to think of the min heap in an instant? We store the weights in the min heap, and just take the root node each time.Screenshot directly here

Huffman coding is actually Huffman treeAn application
It is an unprefixed encoding.No confusion when decoding.It is mainly used in data compression, encryption and decryption, etc.