哈夫曼树

💡 打个比方

想象你要设计一座森林里的快递站：5 种包裹（A、B、C、D、E）每天要送进森林深处的仓库，送 A 包裹的次数最多、送 E 的次数最少。修路很贵，所以你想：送得勤的仓库，修短一点的路；送得少的仓库，路长一点也没关系。怎么修才能让"每天跑的总路程"最少？

答案就是哈夫曼树：把每个包裹的"使用次数"（频率）标在树叶上，然后每次把最轻的两捆并成一捆，一直并到只剩一捆。最后得到的树，保证"频率 × 路长"的总和最小！

🖼️ 大图看明白

5 个字母的频率：A=1、B=4、C=6、D=8、E=10。右边是"每次合并最轻两捆"的全过程，左边是最后得到的哈夫曼树。

💻 完整代码

两段代码：第一段用最小堆直接算 WPL（捷径法）；第二段真的把树建出来，再用 BFS 数深度验证。

// 代码 1：最小堆建哈夫曼树，顺手算 WPL（捷径法）
#include <bits/stdc++.h>
using namespace std;

int main() {
    int freq[] = {1, 4, 6, 8, 10};  // A B C D E
    int n = 5;

    priority_queue<int, vector<int>, greater<int>> pq;  // 最小堆
    for (int i = 0; i < n; i++) pq.push(freq[i]);

    long long wpl = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();   // 最轻的两捆
        int b = pq.top(); pq.pop();
        int s = a + b;                // 新节点权重
        wpl += s;                     // 每个内部节点只加一次 = WPL
        pq.push(s);
    }
    cout << "WPL = " << wpl << endl;  // 输出：WPL = 63
    return 0;
}

// 代码 2：真建一棵树，BFS 数每个字母的深度，验证 WPL
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int w;        // 权重
    int ch;       // 字母编号；-1 表示内部节点
    int l, r;     // 左右孩子编号；0 表示没有
    Node(int weight, int c) : w(weight), ch(c), l(0), r(0) {}
};

int main() {
    int freq[] = {1, 4, 6, 8, 10};   // A B C D E
    int n = 5;
    vector<Node> pool;               // 节点池，编号 = 下标
    // 最小堆存 (权重, 编号)，权重相同比编号
    priority_queue<pair<int,int>, vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;
    for (int i = 0; i < n; i++) {
        pool.push_back(Node(freq[i], i));
        pq.push({freq[i], i});
    }

    while (pq.size() > 1) {
        int a = pq.top().second; pq.pop();   // 较轻的
        int b = pq.top().second; pq.pop();   // 较重的
        pool.push_back(Node(pool[a].w + pool[b].w, -1));
        int id = (int)pool.size() - 1;
        pool[id].l = a;                    // 轻的放左、重的放右（约定）
        pool[id].r = b;
        pq.push({pool[id].w, id});
    }
    int root = pq.top().second;

    // BFS 求每个字母深度，累加 频率 × 深度
    long long wpl = 0;
    queue<pair<int,int>> q;   // {节点编号, 深度}
    q.push({root, 0});
    while (!q.empty()) {
        int id = q.front().first, d = q.front().second;
        q.pop();
        if (pool[id].ch >= 0) wpl += 1LL * pool[id].w * d;
        if (pool[id].l) q.push({pool[id].l, d + 1});
        if (pool[id].r) q.push({pool[id].r, d + 1});
    }
    cout << "WPL = " << wpl << endl;   // 输出：WPL = 63
    return 0;
}

✋ 你来试试