哈夫曼树：带权路径长度WPL最短的多叉树（最优多叉树）
考虑构造一棵包含n个叶子结点的k叉树，其中第i个叶子节点带有权值
w
i
w_i
wi?，要求最小化
∑
w
i
?
l
i
\sum{w_i*l_i}
∑wi??li?,其中
l
i
l_i
li?表示第i个叶子节点到根节点的距离。
——李煜东《算法竞赛进阶指南》
先看一道简单的二叉哈夫曼树：
P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
每次取出堆顶的两个合并入堆即可。
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int n,sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
q.push(x);
}
for(int i=1;i<n;i++)
{
int a=q.top();
q.pop();
int b=q.top();
q.pop();
sum+=(a+b);
q.push(a+b);
}
cout<<sum;
return 0;
}
此题也有加强版，不过与是排序优化：P6033 [NOIP2004 提高组] 合并果子 加强版
了解Huffman编码：
鸣谢：LiberShip
哈夫曼编码原则： n个节点的哈夫曼树含有2n-1个节点，没有度为1的节点 编码从叶子节点到根节点，译码从根节点到叶子节点。
从哈夫曼树根节点开始，对左子树分配码“0”，右子树分配码“1”，一直到达叶子节点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。
例子
一篇电文，原文为：AMCADEDDMCCAD。现在要把原文转换成01串发送给对方。为了节省资源，我们当然希望翻译好的01串长度尽量的短。怎么办？
研究发现：1、只有5个字母E,M,C,A,D； 2、这5个字母的使用频度分别为｛E,M,C,A,D｝= ｛1,2,3,3,4｝。
用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，在树枝上标注分配码“0”或“1”（注：分配码不是边的长度，而是区分左右孩子代表方向）:各字母的编码即为哈夫曼编码： EMCAD
所有编码长度和为12位，即PL=12，此时的PL并不是最小的，但此时的WPL一定是最小的。WPL最小才能使得密报翻译的01串长度最短。
P.S.解码：
正向最大匹配算法：
。字典中最长的key的长度是n
。从左往右扫描要解码的文本：第一次扫描n个字符，如果字典中有匹配的key则用该key对应的value替换这n个字符，如果无匹配的key则n=n-1，再次扫描
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct Node
{
ll w,h;
bool operator <(const Node &a)const
{
if(a.w!=w) return a.w<w;
else return a.h<h;
}
};
ll n,k,ans;
priority_queue<Node>q;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
ll x;
scanf("%lld",&x);
q.push(Node{x,1});
}
while((q.size()-1)%(k-1)!=0)//补成一个完整的哈夫曼树
q.push(Node{0,1});
while(q.size()>=k)
{
ll sum=0,high=-1;
for(int j=1;j<=k;j++)
{
Node temp=q.top();
q.pop();
high=max(high,temp.h);//务必求出最大高度！
sum+=temp.w;
}
ans+=sum;
//cout<<"ans:"<<ans<<endl;
//cout<<"sum:"<<sum<<" high:"<<high<<endl;
q.push(Node{sum,high+1});
}
printf("%lld\n%lld",ans,q.top().h-1);
return 0;
}
PTA-哈夫曼编码（30分）
给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出现频率对应为 4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套编码都可以把原文压缩到 14 个字节。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。
输入
首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：
c[1] f[1] c[2] f[2] ... c[N] f[N]
1
其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：
c[i] code[i]
1
其中c[i]是第i个字符；code[i]是不超过63个’0’和’1’的非空字符串。
输出
对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。
注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。
输入样例
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11
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
输出样例
Yes
Yes
No
No
最优编码并不一定通过哈夫曼算法得到，但是哈夫曼算法得到的一定是最优编码，由此计算得到的带权路径长度(WPL)便是最短的。先将输入中的各大编码方式计算出其对应的带权路径长度之和，与通过哈夫曼算法得到的WPL进行比较，完成第一轮筛选。若是与哈夫曼算法得到的WPL相等，那么再对该编码方式进行前缀判定，存在前缀包含则判错（如果一个字母的编码是另一个字母编码的前缀，解码的结果就不唯一），否则输出Yes。
#include<bits/stdc++.h>
using namespace std;
int c[100],f[100],n,m,WPL;
string code[100];//存储序列
char ch[100];
map<char,int> mp;
priority_queue<int,vector<int>,greater<int> >q;
bool judge()
{
int a,b,sum=0;
for(int i = 0;i<n;++i)
{
for(int j = i+1;j<n;++j)
{
a = code[i].find(code[j]);
//前缀判断，返回code[j]在code[i]中存在的第一个位置，不存在则返回-1
b = code[j].find(code[i]);
//cout<<a<<' '<<b<<endl;
if(!a||!b) return false;
}
sum+=mp[ch[i]]*code[i].length();//计算当前wpl
}
//cout<<"sum"<<sum<<endl;
if(sum==WPL) return true;
else return false;
}
int main()
{
cin>>n;
for(int i = 0;i<n;++i)
{
scanf(" %c %d",&c[i],&f[i]);
q.push(f[i]);
mp[c[i]] = f[i];//存储字母的权值
}
while(q.size()>1)
{
int a=q.top();
q.pop();
int b=q.top();
q.pop();
WPL+=(a+b);
q.push(a+b);
}
//cout<<"WPL"<<WPL<<endl;
cin>>m;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
scanf(" %c",&ch[j]);
cin>>code[j];
}
if(judge()) cout <<"Yes"<<endl;
else cout <<"No"<<endl;
}
return 0;
}
发现了，我只是个搬运工。。。
