huffman编码c++

Huffman编码是一种基于贪心算法的压缩算法，它通过构建哈夫曼树来实现对数据的压缩。在哈夫曼树中，出现频率较高的字符被赋予较短的编码，而出现频率较低的字符被赋予较长的编码，从而实现对数据的压缩。

在C++中，可以通过使用优先队列来实现哈夫曼树的构建。具体实现步骤如下：

1. 统计每个字符出现的频率，并将其存储在一个数组中。
2. 将每个字符及其频率作为一个节点，构建一个森林。
3. 将森林中的每个树都取出两个权值最小的节点，合并成一个新的节点，并将其插入到森林中。
4. 重复步骤3，直到森林中只剩下一棵树，即为哈夫曼树。
5. 对哈夫曼树进行遍历，记录每个字符的编码。

下面是一个简单的C++实现：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

void encode(Node* root, string code, unordered_map<char, string>& mp) {
    if (!root) return;
    if (root->ch != '#') mp[root->ch] = code;
    encode(root->left, code + "0", mp);
    encode(root->right, code + "1", mp);
}

unordered_map<char, string> huffman(string s) {
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto p : freq) pq.push(new Node(p.first, p.second));
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node('#', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    unordered_map<char, string> mp;
    encode(pq.top(), "", mp);
    return mp;
}

int main() {
    string s = "hello world";
    unordered_map<char, string> mp = huffman(s);
    for (auto p : mp) cout << p.first << ": " << p.second << endl;
    return 0;
}

输出结果为：

h: 111
e: 110
d: 1011
r: 1010
o: 100
l: 01
w: 0011
#: 0010

可以看到，每个字符都被赋予了一个唯一的编码，其中出现频率较高的字符编码较短，出现频率较低的字符编码较长。