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

使用最小堆来解决，构建哈夫曼树

从优先队列中取出两个最小的频率 合并成一个新的结点

将新的节点重新插入堆中

重复n - 1次 直到堆中只剩下1个节点为止

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


int main() {
    int n;
    cin >> n;
    priority_queue<long long, vector<long long>,greater<>> heap;
    for(int i = 0; i < n; i ++){
        int cnt;
        cin >> cnt;
        heap.push(cnt);
    }
    long long minLength = 0;
    while(heap.size() > 1){
        long long first = heap.top();
        heap.pop();
        long long second = heap.top();
        heap.pop();

        long long sum = first + second;
        minLength += sum;
        heap.push(sum);
    }
    cout << minLength << endl;
    return 0;
}