哈夫曼树write up

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 定义哈夫曼树节点结构体
struct HuffmanNode {
    int weight;
    HuffmanNode* left;
    HuffmanNode* right;
    
    HuffmanNode(int w) : weight(w), left(nullptr), right(nullptr) {}
};

// 比较函数，用于优先队列
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 计算哈夫曼树的带权路径长度
int calculateWPL(HuffmanNode* root, int depth) {
    if (!root) return 0;
    if (!root->left && !root->right) return root->weight * depth;
    return calculateWPL(root->left, depth + 1) + calculateWPL(root->right, depth + 1);
}

int main() {
    int n;
    cin >> n;
    
    vector<int> weights(n);
    for (int i = 0; i < n; ++i) {
        cin >> weights[i];
    }
    
    // 创建优先队列（最小堆）
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    
    // 将所有字符及其频度插入优先队列
    for (int weight : weights) {
        pq.push(new HuffmanNode(weight));
    }
    
    // 构造哈夫曼树
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        
        HuffmanNode* newNode = new HuffmanNode(left->weight + right->weight);
        newNode->left = left;
        newNode->right = right;
        
        pq.push(newNode);
    }
    
    // 根节点即为哈夫曼树的根
    HuffmanNode* root = pq.top();
    
    // 计算带权路径长度
    int wpl = calculateWPL(root, 0);
    cout << wpl << endl;
    
    return 0;
}