题解 | #【模板】哈夫曼编码# ✅✅✅不构建哈夫曼树求解

关键词：哈夫曼编码 / 贪心算法

核心思想：无需构建完整的哈夫曼树，可以利用贪心策略和优先队列（最小堆），直接算哈夫曼编码的最小成本WPL（编码后字符串的最短长度）。

解题步骤：

1. 输入和初始化：读取每个字符的出现次数，并将其存入一个优先队列（最小堆）中。其中 greater<> 比较器确保队列内元素降序排列。
2. 合并操作：只要优先队列中剩余的元素大于1，就进行以下操作：
1. 从优先队列中取出两个最小的元素a和b。
2. 计算这两个元素合并后的成本a + b，并将该成本累加到结果变量res中。
3. 将合并后的元素a + b重新压入优先队列。
3. 输出结果：当优先队列中只剩下一个元素时，res即为所有合并操作的总成本（编码后字符串的最短长度）。

算法复杂度：时间复杂度O(nlogn)，属于此类问题的最低时间复杂度；空间复杂度O(n)。

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

int main() {
    int n, x;
    cin >> n;
    // 定义一个优先队列，存储字符出现的次数
    // 使用greater<>比较器，使得队列顶部始终是最小的元素
    priority_queue<long long, vector<long long>, greater<>> que;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        que.push(x);
    }

    long long res = 0; // 初始化结果变量res，用于累加所有合并操作的成本
    // 当优先队列中剩余元素大于1时，继续合并操作
    while (que.size() > 1) {
        // 从优先队列中取出两个最小的元素
        long long a = que.top();
        que.pop(); // 第一个最小元素
        long long b = que.top();
        que.pop(); // 第二个最小元素

        // 计算这两个元素合并后的成本，并累加到res中
        res += a + b;
        // 将合并后的元素重新压入优先队列
        que.push(a + b);
    }

    // 最终的res就是编码后字符串的最短长度
    cout << res << endl;
    return 0;
}

}