priority_queue 实现二元霍夫曼编码
2018年5月22日priority_queue 是 C++ 标准库里的优先队列，利用它可以很方便地实现二元霍夫曼编码。
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 10000;
struct node {
string symbol, coding;
double p;
int weight;
int index;
int left, right;
// 重载操作符，用于在优先队列里进行比较
// 优先取概率低的，概率一样时，取编码次数较少的，可以让编码率更高
bool operator < (const node &a) const {
return p != a.p ? p > a.p : weight > a.weight;
}
} s[N];
// 从霍夫曼树的根节点遍历，遍历到子节点时给它编码
void coding(int index, string c)
{
int end = 1;
if (s[index].left != 0) {
coding(s[index].left, c + '0');
end = 0;
}
if (s[index].right != 0) {
coding(s[index].right, c + '1');
end = 0;
}
if (end == 1) {
s[index].coding = c;
}
}
int main()
{
int n;
priority_queue<node> que;
cout << "Please enter the number of symbols";
cin >> n;
cout << "Please these symbols and probability:" << endl;
int cnt = 0;
while (++cnt <= n) {
cin >> s[cnt].symbol >> s[cnt].p;
s[cnt].left = s[cnt].right = 0;
s[cnt].weight = 1;
s[cnt].index = cnt;
que.push(s[cnt]);
}
// 对于二元编码，我们只需要编码 n - 1 次，就可以得到一棵霍夫曼树
for (int i = 0; i < n - 1; i++) {
node first = que.top(); que.pop();
node second = que.top(); que.pop();
s[cnt].p = first.p + second.p;
s[cnt].weight = first.weight + second.weight;
s[cnt].left = first.index;
s[cnt].right = second.index;
s[cnt].index = cnt;
que.push(s[cnt]);
cnt++;
}
coding(cnt - 1, "");
double L = 0.0; // 计算平均编码长度
for (int i = 1; i <= n; i++) {
printf("[%4.2lf] %s: %s\n", s[i].p, s[i].symbol.c_str(), s[i].coding.c_str());
L += s[i].coding.length() * s[i].p;
}
printf("Average code length: %.3lf\n", L);
return 0;
}
