基于贪心法求解哈夫曼编码问题的c++代码

以下是基于贪心法求解哈夫曼编码问题的C++代码：

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
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 cmp {
    bool operator()(node* a, node* b) {
        return a->freq > b->freq;
    }
};

void encode(node* root, string str, unordered_map<char, string>& huff) {
    if (!root) return;
    if (!root->left && !root->right) {
        huff[root->ch] = str;
    }
    encode(root->left, str + "0", huff);
    encode(root->right, str + "1", huff);
}

void huffman(string text) {
    unordered_map<char, int> freq;
    for (char c : text) {
        freq[c]++;
    }

    priority_queue<node*, vector<node*>, cmp> pq;
    for (auto p : freq) {
        pq.push(new node(p.first, p.second));
    }

    while (pq.size() > 1) {
        node* a = pq.top(); pq.pop();
        node* b = pq.top(); pq.pop();
        node* c = new node('$', a->freq + b->freq);
        c->left = a;
        c->right = b;
        pq.push(c);
    }

    node* root = pq.top();
    unordered_map<char, string> huff;
    encode(root, "", huff);

    for (auto p : huff) {
        cout << p.first << ": " << p.second << "\n";
    }
}

int main() {
    string text = "this is an example for huffman encoding";
    huffman(text);
    return 0;
}

这段代码使用了优先队列（priority queue）来实现贪心选择最小的两个节点生成新节点的过程。然后通过递归遍历哈夫曼树生成每个字符的编码，并将其存储在一个 unordered_map 中。最终输出每个字符对应的编码。