定义：
- 1.二叉哈夫曼树：对于一个数列，构建一棵树上带权路径之和最小的二叉树（当然可以\(k\)叉）
- 2.树上带权路径：每个叶子节点到根节点的路径上所有节点的点权\(w\)和到跟的路径长度\(dis\)的乘积之和
简单来说，哈夫曼树满足\(\sum w_i\times dis_i\)最小
基本构造方法：
前置知识（没做过也可以，但至少要会优先队列）：合并果子
一点没错，就是合并果子。你考虑这么一件事，我们想要的就是权值越大的店越靠近根节点，这样\(w_i\)越大\(dis_i\)越小显然更优。那每次找两个最小权值合并就行了。
具体的步骤如下：
- 1.将\(n\)个元素创建\(n\)个节点并视为\(n\)棵树，权值\(w_i\)即为元素\(a_i\)
- 2.选择权值最小的两个根节点\(x,y\)，创建一个虚拟节点，并将左右子树设为\(x,y\)，权值为\(x+y\)（相当于把这两棵树合并了）
- 3.重复步骤2直到成为一棵树
拿一个序列过来演示一下：\(1\) \(9\) \(8\) \(0\) \(4\)
把\(0\)和\(1\)合并：
继续合并：
完成！
哈夫曼编码：
哈夫曼树通常和哈夫曼编码一起使用，什么是哈夫曼编码呢？
我们截取小明一天给他同学发的短信：
- 1.我今天又爆零了
- 2.我中午吃的面
- 3.今天考试爆零的好多
这些消息在二进制下就是一堆\(01\)串，而且在正常编码的情况下每个汉字占的字节都一样多。我们知道传输信息要消耗能量，那么能不能让传输的字符串短一点呢。
一种思路是：让使用更为频繁的汉字编码尽可能的短，比如上文的三句话中，“我”这个字出现次数多，编成\(0\),“面”这个字不怎么常用，编成\(10101100\)。
可还有一个问题，假设“我”是\(0\)，“今”是\(1\),“天”是\(10\),那么\(10\)既可以表示“天”，同时也是“我今”。
怎么解决这个问题呢？我们观察上面构造的哈夫曼树，发现每个原节点都是叶子节点，这是显然的，那么就不可能出现一个节点的编码是另一个的前缀。我们只需要把每个字的使用次数当作权值建立哈夫曼树，从根节点开始，向左在字符串后加一位\(0\)向右走加一位\(1\),每个叶子节点的哈夫曼编码就构造完成了。
\[ps:哈夫曼编码可能有前导零 \]例题：
1.HDU - 1053 Entropy
第一个答案是正常编码的长度，众所周知一个字符长度为\(8\)个比特，直接输出$8\times $长度
第二个答案是哈弗曼编码的长度，你不用真的建树（建了当然也可以），直接用合并果子就行。但要特判只有一种字符的情况（根本不合并）
第三个答案是前两个的比值
CODE:
#include<iostream>
#include<queue>
#define int long long
using namespace std;
int ans1,ans2;
double ans3;
string s;
priority_queue<int, vector<int> , greater<int> > q;
int times[100];
signed main(){
while(cin>>s && s!="END"){
ans2=0;
ans1=s.size()*8;
for(int i=0;i<=26;i++) times[i]=0;
for(int i=0;i<s.size();i++){
if(s[i]!='_') times[s[i]-'A']++;
else times[26]++;
}
for(int i=0;i<=26;i++){
if(times[i]) q.push(times[i]);
}
while(q.size()>1){
int aa=q.top();
q.pop();
int bb=q.top();
q.pop();
q.push(aa+bb);
ans2+=(aa+bb);
}
if(!ans2) ans2=q.top();
ans3=(1.0*ans1)/(1.0*ans2);
cout<<ans1<<" "<<ans2<<" ";
printf("%.1lf",ans3);
cout<<endl;
while(q.size()) q.pop();
}
return 0;
}
2.P2168 [NOI2015] 荷马史诗
一眼哈夫曼树，可是是\(k\)叉。
其他都没有区别，第一问就是最大深度减一。值得注意的是因为最后一次合并不一定有\(k\)个根节点，所以可能出现这种情况（k=3)：
显然\(3,4\)号节点应该放上去。
于是我们一开始不停插入权值为\(0\)的节点直到最后一次合并有\(k\)个根节点，因为其他的权值都比\(0\)大，所以\(0\)会在最下面，其他的节点自然就上去了。
CODE:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans=0;
int n,k;
struct node{
int w,deep;
bool operator<(const node &a)const{
if(w==a.w) return deep>a.deep;
return w>a.w;
}
};
priority_queue<node> q;
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
int siz;
cin>>siz;
node pus;
pus.deep=1;
pus.w=siz;
q.push(pus);
}
while((q.size()-1)%(k-1)!=0){
node pus;
pus.deep=1;
pus.w=0;
q.push(pus);
}
while(q.size()>=k){
int h=0,w=0;
for(int i=1;i<=k;++i){
node t=q.top();
q.pop();
h=max(h,t.deep);
w+=t.w;
}
ans+=w;
node pus;
pus.deep=h+1;
pus.w=w;
q.push(pus);
}
cout<<ans<<endl<<q.top().deep-1;
return 0;
}