【数据结构】【模板】哈夫曼树

哈夫曼树

定义

带权路径长度：结点的权值乘以结点到跟的距离。

树上所有结点带权路径长度之和最小的二叉树称为哈夫曼树。

性质

1. 哈夫曼是满二叉树。
   来自维基百科：
   
2. 原序列构成哈夫曼树的所有叶子结点。
3. 离根结点越近，点权越大。
4. 非叶子结点的点权之和就是所有叶子结点的带权路径之和。
5. 哈夫曼树的叶子结点数量为 \(n\)，则总结点数为 \(2n - 1\)。

建树

构建圆点和方点，圆点代表权值，方点用来建树。

每个方点连接 1 个方点和 1 个圆点或者两个方点，\(n - 1\) 个方点将 \(n\) 个点连接起来，权值为其子节点的权值之和。

构建出来的树要求权值之和最小。

代码实现

最开始时先将所有权值放入优先队列，然后从中取出 2 个点并重新将这两个点的权值之和放入优先队列，这就完成一次方点连接。

模板

模板：P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

其实这也不能算模板

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n;
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }
    int ans = 0;
    while (pq.size() > 1) {
        int p1= pq.top();
        pq.pop();
        int p2 = pq.top();
        pq.pop();
        pq.push(p1 + p2);
        ans += p1 + p2;
    }
    cout << ans << '\n';
    return 0;
}

哈夫曼编码

应用

减少字符串存储需要的空间。

统计一个字符串中每个字符出现的次数，将其作为每个字母的权值，然后建成哈夫曼树。