Huffman 编码
进阶Huffman 编码用贪心合并最小频率节点来缩短平均码长。
// 算法讲解
Huffman 编码
输入正整数频率，观察 Huffman 树的构建过程。
待机
速度 中
待机 ⌨1struct Node {
2 int freq;
3 char ch;
4 Node *left, *right;
5};
6
7struct Cmp {
8 bool operator()(Node* a, Node* b) { return a->freq > b->freq; }
9};
10
11Node* buildHuffman(vector<pair<char,int>>& freqs) {
12 priority_queue<Node*, vector<Node*>, Cmp> pq;
13 for (auto& [ch, f] : freqs)
14 pq.push(new Node{f, ch, nullptr, nullptr});
15 while (pq.size() > 1) {
16 Node* a = pq.top(); pq.pop();
17 Node* b = pq.top(); pq.pop();
18 pq.push(new Node{a->freq + b->freq, 0, a, b});
19 }
20 return pq.top();
21}
复杂度分析
时间 O(n log n)
空间 O(n)
最优 O(n) 两字符时
最坏 O(n log n)
算法讲解
Huffman 编码的核心是：每次从所有可用节点中取出频率最小的两个合并，形成一棵带权路径长度最小的二叉树。
频率高的字符离根更近，编码更短；频率低的字符离根更远，编码更长。
因为任何前缀编码都对应一棵二叉树，而 Huffman 树的带权路径长度是最小的，所以平均码长最优。
理解它的关键是把"合并"和"贪心"联系起来：每次选最小两个，不会让后续选择变得更差。