题解 BNDS OJ 1575 哈夫曼

前置芝士：

哈夫曼树

简要题意：

给定一个仅包含小写字母的字符序列，要求输出这个序列的哈夫曼编码

分析/求解：

哈夫曼建树时要求每次配对权值最小的两个儿子，它们配对所产生的父亲也要重新与其它的树进行比较，所以我们很容易可以想到通过优先队列来维护当前所有的树，具体细节见代码

AC代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

namespace SHAWN {
    const int N = 1e6 + 7;
    struct node { int ma,val,fa,l,r,pos; };
    // ma,val,fa,l,r,pos分别表示当前节点对应的字母，出现的数量，父节点编号，左右儿子编号，当前节点编号
    struct cmp{
        bool operator()(const node&a, const node&b)const{
            if(a.val != b.val) { return a.val > b.val; }
            else { return a.ma > b.ma; }
        }
    };// 重载函数调用运算符
    priority_queue<node,vector<node>,cmp> q; 
    // 用优先队列来维护森林
    string s;
    node tree[N];
    // tree[]维护整棵哈夫曼树
    vector<int> haff[30];
    // haff[]维护每个字母对应的哈夫曼编码
    int used[30];
    // used[]维护每个字母出现的次数
    int n, m, idx;
    void build() {
        while (q.size() >= 2) { // 森林中还有元素时持续配对
            node x = q.top(); q.pop();
            node y = q.top(); q.pop();
            // 取出堆顶两个元素配对
            if (!x.pos) { tree[++idx] = x; tree[idx].pos = x.pos = idx; }
            if (!y.pos) { tree[++idx] = y; tree[idx].pos = y.pos = idx; }
            // 如果取出的点没有在树中则新建一个树上节点
            node z = {-1,(x.val+y.val), -1, x.pos, y.pos, ++idx};
            tree[x.pos].fa = tree[y.pos].fa = idx;
            q.push(z); tree[idx] = z;
            // 建立这两个节点的父亲并扔进森林
        }
    }
    void solve() {
        for (int i = 1; i <= idx; ++i) {
            // 遍历树上节点找到最原始的代表单独字符的节点
            if (tree[i].ma != -1) {
                int now = i;
                while (tree[now].fa != -1) {
                    if (now == tree[tree[now].fa].l) { haff[tree[i].ma].push_back(0); }
                    else { haff[tree[i].ma].push_back(1); }
                    now = tree[now].fa;
                    // 向上搜索找根来获取编码
                }
            }
        }
        for (int i = 1; i <= 27; ++i) {
            if (haff[i].size()) {
                for(int j = haff[i].size()-1; j >= 0; --j) { cout << haff[i][j]; }
                // 由于获取编码时是反向获取的，所以倒序输出
                cout << '\n';
            }
        }
        for (int i = 0; i <= n; ++i) {
            int a = s[i] - 'a' + 1;
            for(int j = haff[a].size()-1; j >= 0; --j) { cout << haff[a][j]; }
            // 查询并输出整个字符串的哈夫曼编码
        }
    }
    int work()
    {
        cin >> n >> m >> s;
        for (int i = 0; i < n; ++i) { used[s[i] - 'a' + 1]++; }
        // 统计每个字母出现的次数
        for (int i = 1; i <=26; ++i) { 
            if (used[i]) { // 如果存在当前字母
                q.push({i,used[i],0,-1,-1,0}); 
                // 将该节点作为一个子树插入森林
            }
        }
        build(); // 建树
        solve(); // 求霍夫曼编码
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}