赫夫曼编码问题贪心算法c++

赫夫曼编码是一种无损数据压缩算法，它是通过将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示来进行压缩的。而贪心算法则是赫夫曼编码中用于构建哈夫曼树的主要算法。

贪心算法的思路是，每次从剩余的未编码字符中找到出现频率最小的两个字符进行合并，并将它们作为一个新的子节点插入到哈夫曼树中。这样，每次合并都能保证当前合并后的节点权值最小，从而最终构建出一棵最优的哈夫曼树。

以下是C++实现赫夫曼编码问题贪心算法的示例代码：

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

using namespace std;

// 定义哈夫曼树节点结构体
struct Node {
    char ch;  // 节点代表的字符
    int freq; // 字符出现的频率
    Node *left, *right; // 左右子节点指针

    Node(char ch, int freq) : ch(ch), freq(freq), left(NULL), right(NULL) {}
};

// 定义优先队列比较函数
struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树并返回根节点指针
Node* buildHuffmanTree(vector<pair<char, int>>& freq) {
    // 将每个字符及其出现频率转换为哈夫曼树节点，并加入优先队列中
    priority_queue<Node*, vector<Node*>, cmp> 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('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    return pq.top();
}

// 递归遍历哈夫曼树，生成编码表
void generateCodeTable(Node* root, string code, vector<pair<char, string>>& codeTable) {
    if (!root) return;
    if (root->ch != '\0') {
        codeTable.push_back(make_pair(root->ch, code));
    }
    generateCodeTable(root->left, code + "0", codeTable);
    generateCodeTable(root->right, code + "1", codeTable);
}

// 主函数
int main() {
    string s = "hello world";
    vector<pair<char, int>> freq(256, make_pair('\0', 0));
    for (char c : s) {
        freq[c].first = c;
        freq[c].second++;
    }

    // 构建哈夫曼树
    Node* root = buildHuffmanTree(freq);

    // 生成编码表
    vector<pair<char, string>> codeTable;
    generateCodeTable(root, "", codeTable);

    // 输出编码表
    for (auto p : codeTable) {
        cout << p.first << ": " << p.second << endl;
    }

    return 0;
}