Huffman树

引入

Huffman 树：设一棵二叉树具有 \(n\) 个带权结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为树的带权路径长度（WPL）

设 \(w_i\) 为二叉树第 \(i\) 个叶结点的权值， \(h_i\) 为从根结点到第 \(i\) 个叶结点的路径长度，则有

对于给定一组带权结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树就是哈夫曼树

实现

构建哈夫曼树

1. 由给定的 \(n\) 个权值构造 \(n\) 棵只有一个根节点的二叉树，得到一个二叉树集合
2. 从二叉树集合中选取根节点权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根节点的权值为其左、右子树根结点的权值和
3. 从二叉树集合中删除作为左、右子树的两棵二叉树，并将新的二叉树加入
4. 重复2，3步，直到二叉树集合只剩下一棵二叉树

设计哈夫曼编码

我们有时需要给每一个元素设计一个编码来表示

在编码时，我们可以让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用相对长的编码，获得更好的空间效率

在设计编码时，要考虑解码的唯一性，即一组编码中任一编码都不是其他编码的前缀

哈夫曼树可以用于构造尽量短的编码，即哈夫曼编码，实现如下：

1. 以出现频率作为每个节点的权值，构建一棵哈夫曼树
2. 设哈夫曼树的左分支为 \(0\) ，右分支为 \(1\) ，则根节点到每个点的路径就是每个元素的编码

应用

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

构造一棵二叉哈夫曼树，输出根节点的权值即可

#include <queue>
#include <cstdio>
using namespace std;

priority_queue<int> q;

int n, ans;

signed main() {
    scanf("%d", &n);

    for (int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        q.push(-x);
    }

    --n;

    for (int x, y; n; --n) {
        x = -q.top(), q.pop();
        y = -q.top(), q.pop(); // 取出两颗权值最小的树,并删去
        ans += x + y;
        q.push(-(x + y)); // 合并
    }

    printf("%d", ans);
    return 0;
}

P2168 [NOI2015] 荷马史诗

Solution：构造一棵 \(k\) 叉哈夫曼树，原理于二叉哈夫曼树类似

Tips：因为每次都是将 \(k\) 个节点合并为 \(1\) 个（减少 \(k-1\) 个），一共要将 \(n\) 个节点合并为 \(1\) 个，如果 \((n-1)\) 不是 \(k-1\) 的倍数，则最后一次合并时不足 \(k\) 个，即最靠近根节点的位置反而没有被排满，因此我们需要加入一些空节点使每次合并都够 \(k\) 个节点，使得 \(n-1\) 是 \(k-1\) 的倍数，利用空节点将其余的节点挤到更优的位置上

Code：

#include <queue>
#include <cstdio>
typedef long long ll;
using namespace std;
const ll inf = 1e18;
const int N = 1e6 + 7;

struct node {
    ll w, h;
    inline bool operator < (const node &y) const {
        return w == y.w ? h > y.h : w > y.w;
    }
};

priority_queue<node> q;

ll n, k;
ll ans;

signed main() {
    scanf("%lld%lld", &n, &k);

    for (int i = 1; i <= n; ++i) {
        ll w;
        scanf("%lld", &w);
        q.push({w, 1});
    }

    while ((q.size() - 1) % (k - 1))
        q.push({0, 1});

    while (q.size() >= k) {
        ll h = 0, w = 0;

        for (ll i = 1; i <= k; ++i) {
            h = max(h, q.top().h), w += q.top().w;
            q.pop();
        }

        ans += w;
        q.push({w, h + 1});
    }

    printf("%lld\n%lld", ans, q.top().h - 1);
    return 0;
}