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

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll ;
int main() {
    int n;
    cin >> n;
    priority_queue<ll, vector<ll> , greater<ll> > q;
    for(int i = 0;i < n;i ++){
        ll x;
        cin >> x;
        q.push(x);
    }
    ll sum = 0;
    while(q.size() > 1){
        ll t1 = q.top();
        q.pop();
        ll t2 = q.top();
        q.pop();
        ll t = t1 + t2;
        q.push(t);
        sum += t;
    }
    cout << sum;
}
// 64 位输出请用 printf("%lld")
//贪心算法（Greedy Algorithm）：

//哈夫曼编码的构建过程是一个典型的贪心算法应用。每次选择当前频率最小的两个节点合并，直到只剩一个节点。

//优先队列（Priority Queue）或最小堆（Min-Heap）：

//高效实现哈夫曼编码的关键是使用优先队列（通常是最小堆）来动态获取当前频率最小的两个节点。

//需要熟悉优先队列的操作（如插入、提取最小值等）及其时间复杂度。