Question d: Haffman coding

Title Description
Huffman code must be familiar to you （ It doesn't matter if I'm not familiar with it , Find out for yourself ...）. Now I give you a string of characters and their corresponding weights , Let you construct Huffman tree , So as to determine the Huffman code of each character . Of course , Here are some small rules ：

1. The left subtree of Huffman tree is coded as 0, The right subtree is coded as 1;

2. If the weight of two characters is the same , be ASCII Characters with small code value are left children , The big one is the right child ;

3. The characters represented by the created new node are the same as those of its child ;

4. All characters are ASCII On the code table 32-96 Characters between （ namely “ ” To “`” Characters between ）.

Input
The input contains multiple sets of data （ No more than 100 Group ）
The first row of each group of data is an integer n, Represents the number of characters . Next n That's ok , Each line has one character ch And an integer weight, According to the character ch The corresponding weight , Space separates the middle .
Input data to ensure that the characters of each group of test data will not be repeated .

Output
For each group of test data , Output the corresponding characters and their Huffman coding results in the input order , See the example for the specific format .

The sample input

3
a 10
b 5
c 8
4
a 1
b 1
c 1
d 1

Sample output

a:0
b:10
c:11
a:00
b:01
c:10
d:11

Ideas ： Top down Huffman coding .

#include <cstdio>
#include <climits>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 110;

struct chardata {
    
    char ch;
    int weight;
} w[maxn];

struct HuffmanNode {
    
    int weight;
    int parent, lchild, rchild;
} Node[maxn * 2];

void searchMin(int &a, int &b, int n) {
    
    int min = INT_MAX;
    // Find the decimal number a
    for (int i = 1; i <= n; i++) {
    
        if (Node[i].parent == 0 && Node[i].weight < min) {
    
            min = Node[i].weight;
            a = i;
        }
    }
    min = INT_MAX;
    // Find the sequence number of the next decimal b
    for (int i = 1; i <= n; i++) {
    
        if (Node[i].parent == 0 && Node[i].weight < min && i != a) {
    
            min = Node[i].weight;
            b = i;
        }
    }
    // Guarantee serial number a Less than serial number b
    if (a > b) {
    
        swap(a, b);
    }
}

void HuffmanCode(int n, chardata *w, char **&ans) {
    
    int m = 2 * n - 1;
    // Initialize original n Leaf node 
    for (int i = 1; i <= n; i++) {
    
        Node[i].parent = Node[i].lchild = Node[i].rchild = 0;
        Node[i].weight = w[i].weight;
    }
    // structure Huffman Binary tree 
    for (int i = n + 1; i <= m; i++) {
    
        int a, b;
        searchMin(a, b, i - 1);
        Node[i].lchild = a;
        Node[i].rchild = b;
        Node[i].weight = Node[a].weight + Node[b].weight;
        Node[i].parent = 0;
        Node[a].parent = Node[b].parent = i; // Mark parent node 
    }
    int c, f, len;
    char temp[n];
    ans = new char *[n + 1];
    for (int i = 1; i <= n; i++) {
    
        c = i;
        len = n;
        temp[len] = 0;
        // Bottom up 
        while (Node[c].parent != 0) {
     // Up to the root node 
            f = Node[c].parent; // Parent node 
            if (Node[f].lchild == c) {
     // Left 0
                temp[--len] = '0';
            } else {
     // Right 1
                temp[--len] = '1';
            }
            c = f; // Keep going up 
        }
        ans[i] = new char[n - len + 1];
        strcpy(ans[i], temp + len); // Copied to the ans
    }
}


int main() {
    
    int n;
    char **ans;
    while (scanf("%d", &n) != EOF) {
    
        for (int i = 1; i <= n; i++) {
    
            getchar();
            scanf("%c %d", &w[i].ch, &w[i].weight);
        }
        HuffmanCode(n, w, ans);
        for (int i = 1; i <= n; i++) {
    
            printf("%c:%s\n", w[i].ch, ans[i]);
        }
    }
    delete ans;
    return 0;
}