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

去打赏