哈夫曼树学习笔记

wangwenhan / 2023-08-24 / 原文

定义：

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$会在最下面，其他的节点自然就上去了。

你可能会问怎么知道插入几个$0$，很简单，第一次是$n$个原节点合并，后面每次是$n-1$个原节点和$1$个虚拟节点合并。所以最后的总结点数$-1$要整除$(k-1)$

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;
}