AIOJ

Weighted Path Length of a Tree

Suppose a binary tree has $n$ weighted leaf nodes. The sum of the products of the path lengths from the root to each leaf and the corresponding leaf weight is called the weighted path length of the tree (Weighted Path Length of Tree, WPL)．

Let $w_i$ be the weight of the $i$ -th leaf node of the binary tree, and let $l_i$ be the path length from the root to the $i$ -th leaf node. The WPL is calculated as follows：

WPL=\sum_{i=1}^nw_il_i

As shown above, the WPL calculation and result are as follows：

WPL=2*2+3*2+4*2+7*2=4+6+8+14=32

Structure

For a given set of leaf nodes with fixed weights, different binary trees can be constructed. Among them, the binary tree with the smallest WPL is called a Huffman tree (Huffman Tree)．

In a Huffman tree, the smaller a leaf node's weight, the farther it is from the root; the larger a leaf node's weight, the closer it is to the root. In addition, only leaf nodes have degree $0$ , while all other nodes have degree $2$ ．

Huffman Algorithm

The Huffman algorithm is used to construct a Huffman tree. Its steps are as follows：

Initialization: Construct $n$ binary trees, each consisting of only one root node, from the given $n$ weights, obtaining a set of binary trees $F$ ．
Selection and merging: Select the two binary trees with the smallest root-node weights from the set of binary trees $F$ and use them as the left and right subtrees to construct a new binary tree. The weight of the root node of this new binary tree is the sum of the weights of the roots of its left and right subtrees．
Deletion and insertion: Delete the two binary trees used as the left and right subtrees from $F$ , and add the newly constructed binary tree to $F$ ．
Repeat steps 2 and 3. When only one binary tree remains in the set, that tree is the Huffman tree．

Proof of Correctness

Lemma

In an optimal prefix-code tree (Huffman tree), the two leaf nodes with the smallest weights are always the deepest leaf nodes, and adjusting these two nodes to be siblings does not destroy the optimality of the coding tree．

Proof

We use proof by contradiction to prove this statement. Suppose that in an optimal prefix-code tree, there are two leaf nodes with the smallest weights that are not the deepest leaf nodes. Let these two nodes be $a$ and $b$ , and suppose their depths are less than that of some deepest leaf node. For this deepest leaf node $c$ , we can swap the position of $a$ with $c$ , or the position of $b$ with $c$ . Since the Huffman algorithm guarantees that the leaf nodes with the smallest weights at each level are merged, after the swap, the weighted path length of the tree (WPL) will decrease. This contradiction shows that the assumption is false, so the two leaf nodes with the smallest weights must be the deepest leaf nodes．

Next, suppose that the two leaf nodes with the smallest weights are $a$ and $b$ , and that they have the same depth. If these two nodes are not siblings in an optimal prefix-code tree, suppose there are other nodes $c$ and $d$ that are siblings of $a$ and $b$ , respectively (suppose $a$ and $c$ are siblings, and $b$ and $d$ are siblings). We can merge $a$ and $b$ into one subtree．

If the sum of the weights of the merged $a$ and $b$ is less than the weight of $c$ or $d$ , we can merge the resulting subtree with the node having the larger weight (such as $c$ or $d$ ) to form a new subtree, which will reduce the WPL．
If the sum of the weights of $a$ and $b$ is no less than the weights of $c$ and $d$ , we can directly adjust $a$ and $b$ to be siblings, with $c$ and $d$ as another pair of siblings; the WPL will not increase．

Therefore, after such an adjustment, optimality is not destroyed. The proof is complete．

Theorem

The prefix-code tree obtained by the Huffman algorithm is an optimal prefix-code tree．

Proof

We use mathematical induction to prove this theorem．

Base case: When the number of letters is $n = 2$ , it is obvious that directly combining the two letters into one tree gives an optimal coding tree．
Inductive hypothesis: Suppose that when the number of letters is $n = k$ （ $k \geq 2$ ）, the Huffman algorithm can obtain an optimal prefix-code tree．
Inductive step: For $n = k + 1$ letters, select the two letters with the smallest weights from the $k+1$ letters and merge them into a subtree, using the root of the subtree as a virtual letter (virtual node). According to the lemma, this operation does not destroy the optimality of the prefix-code tree. At this point, the virtual letter and the remaining $k$ letters together constitute $k + 1$ letters; by the inductive hypothesis, when the number of letters is $k$ , the Huffman algorithm can obtain an optimal prefix-code tree．

Therefore, by mathematical induction, the Huffman algorithm can obtain an optimal prefix-code tree for any number of letters $n$ . The proof is complete．

Huffman Coding

When designing programs, a separate code is usually assigned to each character to represent a set of characters; this is called coding．

When performing binary coding, suppose all codes have the same length. Then representing $n$ different characters requires $\left \lceil \log_2 n \right \rceil$ bits, which is called fixed-length coding．

If every character has the same frequency of use, fixed-length coding is undoubtedly the most space-efficient coding method. If characters occur with different frequencies, however, we can assign as short a code as possible to high-frequency characters and as long a code as possible to low-frequency characters to construct a kind of variable-length coding, thereby achieving better space efficiency．

When designing variable-length codes, the uniqueness of decoding must be considered. If no code in a set of codes is a prefix of any other code, then the set is called a prefix code, which guarantees the uniqueness of decoding．

A Huffman tree can be used to construct the shortest prefix code, namely the Huffman code (Huffman Code). Its construction steps are as follows：

Suppose the character set to be encoded is: $d_1,d_2,\dots,d_n$ , and their frequencies of occurrence in the string are: $w_1,w_2,\dots,w_n$ ．
Use $d_1,d_2,\dots,d_n$ as the leaf nodes and $w_1,w_2,\dots,w_n$ as the leaf-node weights to construct a Huffman tree．
Specify that the left branch of the Huffman coding tree represents $0$ and the right branch represents $1$ . Then the sequence of $0$ s and $1$ s along the path from the root to each leaf node is the code of the character corresponding to that leaf node．

Example Code

Constructing a Huffman Tree

struct HNode {
  int weight;
  HNode *lchild, *rchild;
};

using Htree = HNode *;

Htree createHuffmanTree(int arr[], int n) {
  Htree forest[N];
  Htree root = NULL;
  for (int i = 0; i < n; i++) {  // Store all nodes in the forest
    Htree temp;
    temp = (Htree)malloc(sizeof(HNode));
    temp->weight = arr[i];
    temp->lchild = temp->rchild = NULL;
    forest[i] = temp;
  }

  for (int i = 1; i < n; i++) {  // Build the Huffman tree in n-1 iterations
    int minn = -1, minnSub;  // minn is the index of the root of the minimum-weight tree; minnSub is the index of the root of the second-smallest tree
    for (int j = 0; j < n; j++) {
      if (forest[j] != NULL && minn == -1) {
        minn = j;
        continue;
      }
      if (forest[j] != NULL) {
        minnSub = j;
        break;
      }
    }

    for (int j = minnSub; j < n; j++) {  // Assign values to minn and minnSub
      if (forest[j] != NULL) {
        if (forest[j]->weight < forest[minn]->weight) {
          minnSub = minn;
          minn = j;
        } else if (forest[j]->weight < forest[minnSub]->weight) {
          minnSub = j;
        }
      }
    }

    // Build a new tree
    root = (Htree)malloc(sizeof(HNode));
    root->weight = forest[minn]->weight + forest[minnSub]->weight;
    root->lchild = forest[minn];
    root->rchild = forest[minnSub];

    forest[minn] = root;     // Assign the pointer to the new tree to position minn
    forest[minnSub] = NULL;  // Clear position minnSub
  }
  return root;
}

Calculating the WPL of a Huffman Tree

struct HNode {
  int weight;
  HNode *lchild, *rchild;
};

using Htree = HNode *;

int getWPL(Htree root, int len) {  // Recursively calculate the WPL of an already constructed Huffman tree
  if (root == NULL)
    return 0;
  else {
    if (root->lchild == NULL && root->rchild == NULL)  // Leaf node
      return root->weight * len;
    else {
      int left = getWPL(root->lchild, len + 1);
      int right = getWPL(root->rchild, len + 1);
      return left + right;
    }
  }
}

Directly Calculating the WPL for an Unconstructed Huffman Tree

int getWPL(int arr[], int n) {  // Directly calculate the WPL for an unconstructed Huffman tree
  priority_queue<int, vector<int>, greater<int>> huffman;  // Min-heap
  for (int i = 0; i < n; i++) huffman.push(arr[i]);

  int res = 0;
  for (int i = 0; i < n - 1; i++) {
    int x = huffman.top();
    huffman.pop();
    int y = huffman.top();
    huffman.pop();
    int temp = x + y;
    res += temp;
    huffman.push(temp);
  }
  return res;
}

Calculating Huffman Codes for a Given Sequence

struct HNode {
  int weight;
  HNode *lchild, *rchild;
};

using Htree = HNode *;

void huffmanCoding(Htree root, int len, int arr[]) {  // Calculate Huffman codes
  if (root != NULL) {
    if (root->lchild == NULL && root->rchild == NULL) {
      printf("The code for the character at node %d is: ", root->weight);
      for (int i = 0; i < len; i++) printf("%d", arr[i]);
      printf("\n");
    } else {
      arr[len] = 0;
      huffmanCoding(root->lchild, len + 1, arr);
      arr[len] = 1;
      huffmanCoding(root->rchild, len + 1, arr);
    }
  }
}