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

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

int main() {
    int n;
    cin >> n;
    vector<long long> freq(n);  // 使用 long long 防止大数溢出
    for (int i = 0; i < n; ++i) {
        cin >> freq[i];
    }

    // 使用优先队列（最小堆）
    priority_queue<long long, vector<long long>, greater<long long>> minHeap;
    for (long long num : freq) {
        minHeap.push(num);
    }

    long long totalLength = 0;

    // 合并直到只剩一个节点
    while (minHeap.size() > 1) {
        long long first = minHeap.top(); minHeap.pop();
        long long second = minHeap.top(); minHeap.pop();
        long long merged = first + second;
       
        totalLength += merged;  // 累加合并后的权重
        minHeap.push(merged);
    }

    cout << totalLength << endl;
    return 0;
}

c++中priority_queue容器提供了大小顶堆的数据结构，通过greater或者less<T>来指定大顶还是小顶，依次出栈2个元素构造哈夫曼节点，从而计算权重