c++哈夫曼编码例子

以下是C++实现Huffman编码的例子：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

// 定义Huffman树节点
struct HuffmanNode {
    char ch; // 字符
    int freq; // 频率
    HuffmanNode* left; // 左子节点
    HuffmanNode* right; // 右子节点
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 定义比较函数，用于最小堆的排序
struct cmp {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 构造Huffman树
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> minHeap;
    for (auto& p : freqMap) {
        minHeap.push(new HuffmanNode(p.first, p.second));
    }
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        HuffmanNode* right = minHeap.top();
        minHeap.pop();
        HuffmanNode* parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        minHeap.push(parent);
    }
    return minHeap.top();
}

// 递归获取Huffman编码
void getHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
    if (!root) {
        return;
    }
    if (root->ch != '$') {
        codeMap[root->ch] = code;
    }
    getHuffmanCode(root->left, code + "0", codeMap);
    getHuffmanCode(root->right, code + "1", codeMap);
}

// 打印Huffman编码
void printHuffmanCode(unordered_map<char, string>& codeMap) {
    for (auto& p : codeMap) {
        cout << p.first << " " << p.second << endl;
    }
}

int main() {
    unordered_map<char, int> freqMap = {{'a', 45}, {'b', 13}, {'c', 12}, {'d', 16}, {'e', 9}, {'f', 5}};
    HuffmanNode* root = buildHuffmanTree(freqMap);
    unordered_map<char, string> codeMap;
    getHuffmanCode(root, "", codeMap);
    printHuffmanCode(codeMap);
    return 0;
}