【基本算法】哈夫曼树和哈弗曼编码的C++实现及具体思路（附上哈夫曼树以及优先队列的相关详细知识点补充）

写在前面

这个学期在上算法课的课程，其实也是对本科算法课的扩展和延伸。很多算法以前虽然知道，但是理解不深，并且以前没有动手实践的意识，所以这个学期尽可能的实现每一种重要算法，并且把实现的过程和代码记录下来。

代码实现

#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<string>
using namespace std;
map<int,string>HuffCode;
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int v):val(v),left(NULL),right(NULL)
	{}
	TreeNode():val(0),left(NULL),right(NULL)
	{}	
//不知道为什么，在结构体中重载的<运算符有问题 
//	bool operator<(const TreeNode& node)
//	{
//		return val>node.val;
//	}
};
struct cmp{
	//优先队列重载的都是<号，但是这里注意 val>node->val，其实是val值最小的优先。 
	bool operator()(TreeNode* p1,TreeNode* p2)
	{
		return p1->val>p2->val;
	}
}; 
void PreOrder(TreeNode* node,string s)
{
	if(node!=NULL)
	{
		cout<<node->val<<" ";
	    PreOrder(node->left,s+'0');
	    PreOrder(node->right,s+'1');
	    if(node->left==NULL&&node->right==NULL)
		{
			HuffCode[node->val]=s;
		}
	}
}
int main()
{
	priority_queue<TreeNode*,vector<TreeNode*>,cmp>Huffman;
	int n;
	TreeNode* CurrentNode1,*CurrentNode2,*Head,*NewNode;
	int* input=new int[n];
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>input[i];
	}
	for(int i=0;i<n;i++)
	{
		TreeNode* node=new TreeNode(input[i]);
		Huffman.push(node);
	}
	while(!Huffman.empty())
	{
		CurrentNode1=Huffman.top();
		Huffman.pop();
		if(Huffman.empty())
		{
			Head=CurrentNode1;
			break;
		}
		else
		{
			CurrentNode2=Huffman.top();
			Huffman.pop();
		}
		NewNode=new TreeNode;
		NewNode->left=CurrentNode1;
		NewNode->right=CurrentNode2;
		NewNode->val=CurrentNode1->val+CurrentNode2->val;
		Huffman.push(NewNode);
	}
	PreOrder(Head,"");
	cout<<endl;
	for(auto i=HuffCode.begin();i!=HuffCode.end();i++)
	{
		cout<<(*i).first<<" "<<(*i).second<<endl;
	}
	delete[] input;
	return 0;
}

相关知识点补充

（1）哈夫曼编码和哈夫曼树

（2）优先队列

哈夫曼编码问题是需要用贪心算法解决的。贪心算法每次一般都是选择最小的两个频率进行合并，基于这样的解题思路就可以用STL中的优先队列来解决，优先队列是每次选择最小的两个频率进行合并。但是STL中的priority_queue有几个坑要注意一下：
（1）priority_queue也还是队列的一种，只需要#include就行。
（2）priority_queue和queue的目的不同，queue是保证了输入数据的先进先出，而priority_queue是保证每次得到优先级最高的数据。对应在使用上，queue可以通过front和back来分别获得队首和队尾元素，但是priority_queue就只有一个top来得到队首的优先级最高的数据（因为已经不需要获得队尾元素了）。stack也是通过使用top得到栈顶元素。
（3）priority_queue中关于优先级的定义很多时候是需要自定义的，尤其是对于结构体这种对象。自定义的时候有两种方式，一个是在结构体中直接重载<运算符，另一种是在外面定义一个cmp结构体，在这个结构体中重载<运算符。我这次用的是第二种方法。我本来想直接在结构体中重载<运算符，但是发现直接在结构体中重载并没有重载成功（优先队列中的数据没有按照从小到大排好序）。如果有知道原因的，欢迎大佬在评论区评论告知，万分感谢。
（4）priority_queue的格式为priority_queue<Type, Container, Functional>，其中Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，也就是优先队列是大顶堆，队头元素最大。
（5）priority_queue中重载运算符的时候的用法和平时我们使用sort的时候的重载不一样，拿我的这份代码来说，代码中比较函数中的返回是return p1->val>p2->val;但是其实是实现的小顶堆而不是大顶堆，也就是说，实现的是把val值较小的TreeNode放在队首优先级高的位置。而我们平时使用sort的时候return p1->val>p2->val;表示的是按照从大到小的顺序进行排序。所以一定要注意这两个的区别。

思路

思路就是使用一个优先队列，首先把输入的每个数据创建一个TreeNode结点，这些待编码的数据对应的结点就是之后构建的哈夫曼树的叶子结点。之后构建while循环，只要优先队列中还有2个及2个以上的结点，就继续进行合并（这里貌似也可以不用这个while循环，因为哈夫曼树是进行n-1次合并，可以直接做n-1次合并也可）。每次合并的时候就是新创建一个非叶子结点，非叶子结点的左孩子和右孩子就是合并的两个结点，但是要注意合并后的结点要继续push到队列中，参与之后的结点合并。最后把哈夫曼树构建出来，通过先序遍历每次在遍历的同时记录0,1到当前string中（left就是0，right就是1），并且把每个叶子结点与哈弗曼编码的对应关系存放在map中。