哈夫曼编码C++实现

哈夫曼编码就是不断地取数列中最小的两个，合并，再添加到数列中，循环。利用了贪心的思想。在C++实现的时候可以用到优先队列 priority_queue，这个方便的东西。

这个优先队列，会自己进行排序，每次加进去一个数，都会更新，降序排列或升序排列。以升序排列为例，更新过后的队首元素就是数列中最小的数。

priority_queue的用法

首先要用到头文件#include<queue> 定义优先队列：priority_queue<int,vector<int>,greater<int> >q;（这里不需要用到<vector>头文件）其中，greater<int>是升序（从小到大排序），如果是降序（从大到小）就要用less<int>

要注意的是最后两个尖括号不要挨着> >，因为>>是重载运算符，编译器会报错。

然后是一些优先队列的基本操作：

priority_queue<int,vector<int>,greater<int> >q;//定义优先队列 q.push(x);//将x加入到优先队列中 t=q.top();//返回队首元素 q.pop();//弹出队首元素 l=q.size();//返回队列长度（元素个数） b=q.empty();//判断队列是否为空，为空返回1，否则返回0

然后就可以上代码了：

#include <queue> #include <iostream> using namespace std; int main() { int n,a,b,c; priority_queue<int,vector<int>,greater<int> >q; cin>>n; for(int i=0;i<n;i++){ cin>>c; q.push(c); } int ans=0; while(q.size()>1){ a=q.top();q.pop();//取出最小的两个元素 b=q.top();q.pop(); ans=a+b;//合并 q.push(ans);//将合并后的数加入到队列中 } cout<<ans<<endl;//最后编码总长度 return 0; }

代码很短，很简单。