CHAPTER_9  提高篇(3)——数据结构(2)

 

 

9.8.1哈夫曼树

首先来明确两个定义。对于一棵树，我们把叶子节点的权值乘以其路径长度的结果称为这个叶子节点的带权路径长度。例如下图中，叶子节点G的带权路径长度为 3 * 2 = 6 。树的带权路径长度(WPL)等于它所有叶子节点得到带权路径长度之和。对于下面这棵树，其WPL等于3 * 2 + 5 * 2 + 13 * 1 = 29 。

我们有如下问题：已知n个数，寻找一棵树，使得树的所有叶子节点的权值为这n个数，并且使得这棵树的带权路径长度最小。这棵带权路径长度最小的树被称为哈夫曼树(又称最优二叉树)。

寻找这棵树的过程就是给定叶子节点构造哈夫曼树的过程，算法如下：

（1）初始状态共有n个节点(权值分别为给定的n个数)，将它们视作n棵只有一个节点的树。

（2）合并其中根节点权值最小的两棵树，生成两棵树根节点的父亲节点，权值为这两个根节点的           权值和。这样树的数量就减少了一个。

（3）重复操作(2)，直到只剩下一棵树为止。这棵树就是哈夫曼树。

例如上图中，初始有3个节点，权值分别为3、5、13，我们将其实现三棵树。将三棵树中根节点最小的3和5合并，得到一棵根节点为8的树。至此还剩下两棵树，根节点分别为：8、13.将两棵树合并得到一棵树，根节点为21.这就是最终哈夫曼树。

有一点需要注意，对于同一组叶子节点，对应的哈夫曼树可以不唯一，但是最小带权路径长度一定唯一。

实际上在很多实际应用场景中，我们并不需要去实现一棵哈夫曼树。因此需要着重的掌握哈夫曼树的构造思想，也就是反复选择最小的两个元素合并，直到只剩下一个元素。一般可以使用优先队列来执行这种策略。

我们用一个经典问题来演示这种策略：

有n堆果子，每堆果子质量已知。现在需要把这些果子合并成一堆，但是每次只能将两堆果子合并到一起。每次合并果子都会消耗体力，假如某次合并质量为a和b的果堆，消耗的体力为a+b。显然在N-1次合并后，果子最后只剩下一堆了。为了尽可能消耗最少的体力，我们要设计最优的合并次序。显然，最优的策略即为构造哈夫曼树的思想。

我们用优先队列来实现整个过程：

#include<iostream>
#include<queue>

using namespace std;

int main() {
	//代表小顶堆的优先队列 
	priority_queue<long long,vector<long long>,greater<long long> > q;
	int n;
	long long tmp,x,y,ans=0;
	cin>>n;                       //输入果堆数量 
	for(int i=0;i<n;i++) {        //将每个果堆重量压入优先队列 
		cin>>tmp;
		q.push(tmp);
	}
	while(q.size()>1) {           //当优先队列中至少有两个元素 
		x=q.top();
		q.pop();
		y=q.top();
		q.pop();                  //取出最小的两个元素
		ans+=x+y;                 //累计求和结果 
		q.push(x+y);              //将结果压入优先队列 
	}
	cout<<ans<<endl;
	return 0;
}

 

9.8.2哈夫曼编码

在数据传送时，信息表现为0和1的二进制形式。为了提高传输的速度，可以采用变长的编码方式，寻找更优的编码方式。同时，必须要保证编码不存在二义性（任意字符编码都不是其它字符编码的前缀）。

哈夫曼编码就是符合上述要求的编码方式，采用自底向上的形式构造哈夫曼树。按照字符的概率分配码长，实现平均码长最短的编码。

使用需要传送的字符构造字符集C = {c1, c2, ... cn}，并根据字符出现的频率构建概率集W = {w1, w2, ... wn}。哈夫曼编码的流程如下：

• 将字符集C作为叶子节点；
• 将频率集W作为叶子节点的权值；
• 使用C和W构造哈夫曼树；
• 对哈夫曼树的所有分支，左子树分支编码为0，右子树分支编码为1；

通过上述流程，即完成了哈夫曼编码。

这么说可能有些抽象，我们举一个简单的例子。假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1。我们将这五个字符当作叶子节点、出现次数当作权值构造哈夫曼树如下：

然后根据如上哈夫曼树，根据左0右1的规则对每个字符编码，各字符对应的编码为：A->11,B->10,C->00,D->011,E->010。

需要强调的是，哈夫曼树是针对确定字符串而言的，只有确定了字符串，才能统计每个字符出现频次，因此才能构造哈夫曼树。