【数据结构与算法】创建 HuffmanTree 哈夫曼树 (最优二叉树)

《数据结构实验指导 - C++语言版》题目集 算法5-15 创建哈夫曼树

请编写程序，根据给定的权重值序列，构建哈夫曼树，并计算带权路径长度。

输入格式：

输入首先给出一个不超 20 的正整数 n，随后一行给出 n 个权重值。其中权重值都是不超过 100 的正整数。

输出格式：

在一行中输出哈夫曼树的带权路径长度。

输入样例：

5
1 2 3 4 5

输出样例：

33

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int val;
    Node* left;
    Node* right;
    int weight;
    Node(int x, int w):val(x),left(nullptr),right(nullptr),weight(w) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->weight>b->weight;
    }
};

priority_queue<Node*, vector<Node*>, Compare> pq;

Node* BuildHuffmanTree() {
    if (pq.size() < 1) return nullptr;
    if (pq.size() == 1) return pq.top();

    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node(-1,left->weight+right->weight);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

int ans = 0;

void dfs(Node* root, int level) {
    if (root == nullptr) return;
    if (root->left == nullptr && root->right == nullptr) {
        ans += root->weight * level;
    }
    dfs(root->left, level + 1);
    dfs(root->right, level + 1);
}

int main() {
    int n;
    cin>>n;
    for (int i=0;i<n;i++) {
        int b;
        cin>>b;
        Node* node = new Node(i,b);
        pq.push(node);
    }
    Node* root = BuildHuffmanTree();
    dfs(root, 0);
    cout<<ans<<endl;
    return 0;
}