哈夫曼树模板

最优编码树——带权路径长度最短的二叉树

哈夫曼编码优先队列 GESP6

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++) {
        int w; cin >> w;
        pq.push(w);
    }

    // 每次取最小的两个合并
    int totalCost = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        totalCost += a + b;
        pq.push(a + b);
    }

    cout << totalCost << endl;  // 最小带权路径长度
    return 0;
}

📖 要点说明

贪心策略：每次取频率最小的两个节点合并
用小根堆维护，O(n log n)
带权路径长度 = 所有合并代价之和

⚠️ 常见错误

用大根堆（方向搞反）
忘处理 n=1 的特殊情况
混淆 WPL 的计算方式