跳转至

哈夫曼树

在应用到字符串编码时，哈夫曼树可以被理解为某种字典树。每个字符串对应一个叶子节点，因此不会出现两个字符串具有前缀关系。

Note

荷马史诗

你有一篇 \(n\) 个单词的文章，你需要对文章中的所有单词进行编码，满足以下要求：

  • 每个单词的编码都是一个 \(k\) 进制序列；
  • 相同的单词的编码相同；
  • 不同的单词的编码不能存在前缀关系；

要求最小化编码后的文章总长度。

我们先统计每种单词出现的次数，记第 \(i\) 种单词为 \(s_i\)，出现次数为 \(cnt_i\)。

初始时，每种单词都是一个深度为 \(0\) 的节点，也可以理解为所有单词的编码初始时都是空串。我们用结构体记录 \((cnt_i,dep_i)\)。

接着，进行若干次合并，每次合并选择 \(cnt_i\) 最小的 \(k\) 个节点（若有多个 \(cnt\) 相同的节点，取 \(dep\) 更小的），将其合并成一个新节点 \(\big(\sum{cnt_j}, \max\{dep_j\}+1\big)\)。只剩一个节点时，合并结束。

合并的本质是，给选出的所有节点（一个节点代表一个字符串集合）在最前面增加一个字符以此区分它们。体现在哈夫曼树上就是新建一个节点，将选出的 \(k\) 个节点（子树）都作为新节点的儿子。

我们可以使用优先队列优化寻找最小值的过程。

1
2
3
4
5
6
7
8
9
while(que.size() != 1){
    int nCnt = 0, nDep = 0;
    for(int i = 1; i <= k; i++){
        nCnt += que.top().cnt;
        nDep = max(nDep, que.top().dep);
        que.pop();
    }
    que.push({nCnt, nDep + 1});
}

但如果直接这样做，可能会出现队列中元素个数大于 \(1\) 但不足 \(k\) 个的情况。如果哈夫曼树根节点的儿子数量不足 \(k\) 个，那么此种编码方案不一定最优。

我们注意到，一次正常的合并会将节点的数量减少 \(k+1\) 个。因此，我们可以在最开始的时候向队列中添加一些空节点，使得队列中的元素个数 que.size() 满足 que.size()\(\equiv 1\ \big(\text{mod}(k-1)\big)\)。这样可以有效的避免这个问题。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<queue>
#define int long long
using namespace std;
const int N = 1E5 + 10;

struct Node{
    int cnt;
    int dep;
    inline bool operator<(const Node& other) const {
        if(cnt != other.cnt) return cnt > other.cnt;
        return dep > other.dep;
    }
};

int n, k, ans1;
int w[N];
priority_queue<Node> que;

signed main(){

    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
        que.push({w[i], 0});
    }

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

    while(que.size() != 1){
        int nCnt = 0, nDep = 0;
        for(int i = 1; i <= k; i++){
            nCnt += que.top().cnt;
            nDep = max(nDep, que.top().dep);
            que.pop();
        }
        que.push({nCnt, nDep + 1});
        ans1 += nCnt;
    }

    cout << ans1 << endl << que.top().dep << endl;

    return 0;
}