哈夫曼编码贪心算法c++实现

以下是C++中哈夫曼编码的贪心算法实现：

#include <iostream>
#include <queue>
#include <vector>

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* l, Node* r) { return l->freq > r->freq; }
};

// 生成哈夫曼树
Node* huffmanTree(const string& str) {
    // 统计字符频率
    vector<int> freq(256, 0);
    for (auto& c : str) {
        freq[c]++;
    }

    // 构建小根堆
    priority_queue<Node*, vector<Node*>, compare> pq;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            pq.push(new Node(i, freq[i]));
        }
    }

    // 不断合并小根堆中的节点，直到只剩一个节点
    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);
    }
    return pq.top();
}

// 生成哈夫曼编码
void huffmanCode(Node* root, string code, vector<string>& result) {
    if (!root) {
        return;
    }
    if (root->ch != '#') {
        result[root->ch] = code;
    }
    huffmanCode(root->left, code + "0", result);
    huffmanCode(root->right, code + "1", result);
}

int main() {
    string str = "hello world";
    Node* root = huffmanTree(str);

    vector<string> result(256);
    huffmanCode(root, "", result);

    // 输出生成的哈夫曼编码
    for (int i = 0; i < 256; i++) {
        if (!result[i].empty()) {
            cout << (char)i << ": " << result[i] << endl;
        }
    }

    return 0;
}

在这个实现中，我们首先统计字符串中每个字符出现的频率，并将它们存储在一个大小为256的数组中。然后，我们构建一个小根堆，其中每个节点都代表一个字符及其对应的频率，我们将小根堆中频率最小的两个节点合并为一个新节点，并将它们的和作为新节点的频率。这个过程一直持续到小根堆中只剩下一个节点为止，这个节点就是哈夫曼树的根节点。

接下来，我们沿着哈夫曼树，为每个字符生成一个哈夫曼编码。当我们遍历到一个叶子节点时，我们就将其对应的字符和编码存储在一个vector中。

最后，我们可以输出每个字符的哈夫曼编码。