​



————— the next day —————



— — — — — —






Concept 1: What is a path?



In a tree, all the nodes through which you go from one node to another are called paths between two nodes.






In the binary tree above, the path from root A to leaf H is A, B, D, H



Concept 2: What is path length?


In a tree, the number of “edges” passed from one node to another is called the length of the path between two nodes.





Again, using the binary tree example, from root A to leaf H, there are three edges, so the path length is 3




Concept 3: What is the weighted path length of a node?


Each node of the tree can have its own “Weight” (Weight), which can play different roles in different algorithms.


The weighted path length of a node refers to the length of the path from the root of the tree to the node, multiplied by the weight of the node.



Let’s say the weight of node H is 3, and the length of the path from the root to node H is also 3, so the length of the weighted path to node H is 3 X 3 = 9



Concept 4: What is the weighted path length of a tree?


In a tree, the sum of the weighted path lengths of all leaf nodes is called the tree’s weighted path length, also known as WPL for short.


Again, in this binary tree, the path length of the tree is 3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53



The Huffman tree was invented by Dr. Huffman of THE Massachusetts Institute of Technology in 1952. What exactly is this tree?


Just now we learned the weighted path length (WPL) of a Tree, and Huffman Tree is the binary Tree with the minimum weighted path length under the condition that the leaf nodes and weights are determined, also known as the optimal binary Tree.


For example, given a leaf node with a weight of 1,3,4,6,8, what kind of binary tree should we build to ensure the minimum length of its weighted path?


In principle, we should keep leaves with less weight away from the roots and leaves with more weight close to the roots.


The tree on the left is a Huffman tree with a WPL of 46, which is smaller than 53 in the previous example:




It should be noted that there may be more than one Huffman tree formed by the same leaf nodes. The following trees are Huffman trees:






Suppose there are six leaf nodes with weights of 2, 3, 7, 9, 18, and 25. How do you build a Huffman tree with the smallest weighted path length?





Step 1: Build a forest

We treat each leaf node as a tree, a tree in its own right (a tree with only roots), and we form a forest:



In the figure above, on the right is a forest of leaf nodes, and on the left is an auxiliary queue, which stores all leaf nodes according to their weights from small to large. As for the role of secondary queues, we will see later.


Step 2: Select the two nodes with the lowest weight to generate a new parent node

With the help of the auxiliary queue, we can find the nodes 2 and 3 with the lowest weights, and generate a new parent node according to these two nodes. The weight of the parent node is the sum of the weights of these two nodes:




Step 3: Remove the two minimum nodes selected in the previous step from the queue and add the new parent node to the queue

Remove 2 and 3 from the queue, insert 5, and keep the queue in ascending order:




Step 4:Select the two nodes with the lowest weight to generate a new parent node

This is a repeat of step 2. The node with the lowest weight in the current queue is 5 and 7, and the weight of the new parent node is 5+7=12:




Step 5:Remove the two smallest nodes selected in the previous step from the queue and add the new parent node to the queue

This is a repeat of step 3, which removes 5 and 7 from the queue, inserts 12, and still keeps the queue in ascending order:




Step 6:Select the two nodes with the lowest weight to generate a new parent node

This is a repeat of step 2. The node with the lowest weight in the current queue is 9 and 12, and the weight of the new parent node is 9+12=21:




Step 7:Remove the two smallest nodes selected in the previous step from the queue and add the new parent node to the queue

This is a repeat of step 3, which removes 9 and 12 from the queue, inserts 21, and still keeps the queue in ascending order:




Step 8:Select the two nodes with the lowest weight to generate a new parent node

This is a repeat of step 2. The nodes with the minimum weight in the current queue are 18 and 21, and the weight of the new parent node is 18+21=39:




Step 9:Remove the two smallest nodes selected in the previous step from the queue and add the new parent node to the queue

This is a repeat of step 3, which removes 18 and 21 from the queue, inserts 39, and still keeps the queue in ascending order:




Step 10:Select the two nodes with the lowest weight to generate a new parent node

This is a repeat of step 2. The nodes with the lowest weights in the current queue are 25 and 39, and the weight of the new parent node is 25+39=64:




Step 11:Remove the two smallest nodes selected in the previous step from the queue and add the new parent node to the queue

This is a repeat of step 3, which removes 25 and 39 from the queue and inserts 64:



At this point, there is only one node in the queue, indicating that the whole forest has been merged into a tree, and this tree is the Huffman tree we want:




private Node root; private Node[] nodes; Queue<Node> nodeQueue = new PriorityQueue<>(); public void createHuffman(int[] weights) {Queue<Node> nodeQueue = new PriorityQueue<>(); nodes = new Node[weights.length]; // Build the forest and initialize the Nodes arrayfor(int i=0; i<weights.length; i++){ nodes[i] = new Node(weights[i]); nodeQueue.add(nodes[i]); } // The main loop ends when there is only one node left in the queuewhile(nodequeue.size () > 1) {Node left = nodequeue.poll (); Node right = nodeQueue.poll(); // Create a new Node as the parent Node of two nodes Node parent = new Node(left. Weight + right. Weight, left, right); nodeQueue.add(parent); } root = nodeQueue.poll(); } public void output(Node head) {if(head == null){        return; } System.out.println(head.weight); output(head.lChild); output(head.rChild); }public static class Node implements Comparable<Node>{ int weight; Node lChild; Node rChild; public Node(int weight) { this.weight = weight; } public Node(int weight, Node lChild, Node rChild) { this.weight = weight; this.lChild = lChild; this.rChild = rChild; } @Override public int compareTo(Node o) {return new Integer(this.weight).compareTo(new Integer(o.weight));    }}public static void main(String[] args) {    int[] weights = {2,3,7,9,18,25};    HuffmanTree huffmanTree = new HuffmanTree();    huffmanTree.createHuffman(weights);    huffmanTree.output(huffmanTree.root);}Copy the code


In this code, to ensure that nodes in the node queue are always in ascending weight order, we use PriorityQueue.


At the same time, the static inner class Node needs to implement the comparison interface, overriding the compareTo method to ensure that Node objects are compared by weight when queued.







— — the END — — –



Like this article friends, welcome to pay attention to the public number programmer xiao Grey, watch more exciting content


Point [praise], is the biggest support for small grey!Copy the code