题解 | #【模板】哈夫曼编码#

解题思路：

1. 输入字符种数n和每种字符的出现次数ai。
2. 使用最小堆pq来保存每种字符的出现次数，以便每次能够从堆中取出两个出现次数最少的字符。
3. 不断从堆中取出两个最小的节点，合并它们为一个新节点，其出现次数为两者之和，并将新节点放回堆中。
4. 重复步骤3，直到堆中只剩下一个节点，即哈夫曼树的根节点。
5. 遍历哈夫曼树，为每个字符分配一个二进制编码，规则是：左子树赋值为0，右子树赋值为1，从根节点开始赋值。同时记录每个字符的编码长度。
6. 计算编码后字符串的最短长度，即每个字符的编码长度乘以其出现次数的总和。输出结果。

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

using namespace std;

// 定义哈夫曼树节点结构
struct HuffmanNode {
    long long weight;     // 权重，即字符出现次数
    int depth;            // 节点深度，用于计算编码长度
    HuffmanNode *left;    // 左子树指针
    HuffmanNode *right;   // 右子树指针

    HuffmanNode(long long w) : weight(w), depth(0), left(nullptr), right(nullptr) {}
};

// 自定义比较函数，用于构建最小堆
struct CompareHuffmanNodes {
    bool operator()(const HuffmanNode *lhs, const HuffmanNode *rhs) const {
        return lhs->weight > rhs->weight;
    }
};

int main() {
    int n;
    cin >> n; // 输入字符种数

    // 使用最小堆来管理哈夫曼树节点
    priority_queue<HuffmanNode *, vector<HuffmanNode *>, CompareHuffmanNodes> pq;

    for (int i = 0; i < n; i++) {
        long long weight;
        cin >> weight;
        pq.push(new HuffmanNode(weight)); // 创建节点并放入堆中
    }

    while (pq.size() > 1) {
        // 从堆中取出两个最小的节点，构建新节点
        HuffmanNode *left = pq.top();
        pq.pop();
        HuffmanNode *right = pq.top();
        pq.pop();

        HuffmanNode *parent = new HuffmanNode(left->weight + right->weight);
        parent->left = left;
        parent->right = right;

        pq.push(parent); // 将新节点放回堆中
    }

    long long totalLength = 0;
    // 赋值深度并计算路径长度
    if (!pq.empty()) {
        HuffmanNode *root = pq.top();
        root->depth = 0;

        queue<HuffmanNode *> q;
        q.push(root);

        while (!q.empty()) {
            HuffmanNode *node = q.front();
            q.pop();

            if (node->left != nullptr) {
                node->left->depth = node->depth + 1;
                q.push(node->left);
            }

            if (node->right != nullptr) {
                node->right->depth = node->depth + 1;
                q.push(node->right);
            }

            if (node->left == nullptr && node->right == nullptr) {
                totalLength += node->depth * node->weight; // 计算路径长度
            }
        }
    }

    cout << totalLength << endl; // 输出最短长度

    return 0;
}