Question C: Huffman tree

Title Description
Huffman tree , Enter a number in the first line n, Represents the number of leaf nodes . You need to use these leaf nodes to generate a Huffman tree , According to the concept of Huffman tree , These nodes have weights , namely weight, The question needs to output the sum of the product of the value and weight of all nodes .

Input
Input has multiple sets of data .
Enter a number in the first row of each group n, Then the input n Leaf nodes （ The weight of leaf nodes does not exceed 100,2<=n<=1000）.

Output
Output weights .

The sample input

2
2 8 
3
5 11 30 

Sample output

10
62

Train of thought ： Use priority queue to calculate directly .

#include <cstdio>
#include <queue>
using namespace std;

// Priority queue representing small top heap 
priority_queue<int, vector<int>, greater<int>> q;

int main() {
    
    int n, temp, x, y;
    while (scanf("%d", &n) != EOF) {
    
        int sum = 0;
        for (int i = 0; i < n; ++i) {
    
            scanf("%d", &temp);
            q.push(temp);
        }
        while (q.size() > 1) {
    
            x = q.top();
            q.pop();
            y = q.top();
            q.pop();
            q.push(x + y); // The sum of the two is added to the priority queue as a new number 
            sum += x + y;
        }
        q.pop();
        printf("%d\n", sum);
    }
    return 0;
}

Train of thought two ： Construct the Huffman tree , Top down traversal .

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

const int maxn = 1010;
struct HuffmanNode {
    
    int weight, flag;
    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);
    }
}

int HuffmanCode(int n, int *w) {
    
    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];
    }
    // 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[a].parent = Node[b].parent = i; // Mark parent node 
    }
    int ans = 0, len = 0;
    while (m) {
    
        if (Node[m].flag == 0) {
     // towards the left 
            Node[m].flag = 1; // Mark that the left subtree has been accessed 
            if (Node[m].lchild != 0) {
    
                m = Node[m].lchild;
                len++;
            } else if (Node[m].rchild == 0) {
     // leaf node 
                ans += Node[m].weight * len;
            }
        } else if (Node[m].flag == 1) {
     // towards the right 
            Node[m].flag = 2; // Mark that the right subtree has been accessed 
            if (Node[m].rchild != 0) {
    
                m = Node[m].rchild;
                len++;
            }
        } else {
     // return 
            Node[m].flag = 0;
            m = Node[m].parent;
            --len; // Code length minus 1
        }
    }
    return ans;
}

int main() {
    
    int n, w[maxn];
    while (scanf("%d", &n) != EOF) {
    
        for (int i = 1; i <= n; i++) {
    
            scanf("%d", &w[i]);
        }
        int ans = HuffmanCode(n, w);
        printf("%d\n", ans);
    }
    return 0;
}