2. 计算WPL

Huffman编码是通信系统中常用的一种不等长编码，它的特点是：能够使编码之后的电文长度最短。

更多关于Huffman编码的内容参考教材第十章。

输入：
    第一行为要编码的符号数量n
    第二行～第n+1行为每个符号出现的频率

输出：
    对应哈夫曼树的带权路径长度WPL

代码如下：

#include 
#include 
using namespace std;
struct HFTree
{
    int weight;
    HFTree *left;
    HFTree *right;
    HFTree(int weight) : weight(weight), left(nullptr), right(nullptr) {}
};
auto compare = [](HFTree *left, HFTree *right)
{
    return (left->weight > right->weight);
};
int Calculate(HFTree *root, int depth = 0)
{
    if (!root)
        return 0;
    if (!root->left && !root->right)
        return depth * root->weight;
    return Calculate(root->left, depth + 1) + Calculate(root->right, depth + 1);
}
 
int main()
{
    int n;
    cin >> n;
    priority_queue, decltype(compare)> Queue(compare);
    for (int i = 0; i < n; ++i)
    {
        int weight;
        cin >> weight;
        Queue.push(new HFTree(weight));
    }
    while (Queue.size() != 1)
    {
        HFTree *left = Queue.top();
        Queue.pop();
        HFTree *right = Queue.top();
        Queue.pop();
        int sum = left->weight + right->weight;
        HFTree *top = new HFTree(sum);
        top->left = left;
        top->right = right;
        Queue.push(top);
    }
    cout << "WPL=" << Calculate(Queue.top()) << endl;
    return 0;
}