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

哈夫曼编码是一种常用的数据压缩算法，它通过构建一棵哈夫曼树来实现对数据的压缩。其中，哈夫曼树是一种满足最优性质的树，其叶子节点代表原始数据中的字符，而每个字符对应的编码是从根节点到该字符所在叶子节点的路径上的0/1序列。

哈夫曼编码的实现是一个经典的贪心算法，其基本思想是通过不断地合并出现频率最小的两个节点来构建哈夫曼树。具体实现过程如下：

1. 统计每个字符在原始数据中出现的频率，并将其作为叶子节点的权值。

2. 将所有叶子节点按照权值从小到大排序，并依次将它们放入一个最小堆中。

3. 从最小堆中依次取出两个权值最小的节点，并将它们合并为一个新节点，新节点的权值为这两个节点的权值之和。将新节点插入到最小堆中。

4. 重复步骤3，直到最小堆中只剩下一个节点，即为哈夫曼树的根节点。

5. 从根节点开始遍历哈夫曼树，对每个叶子节点记录其对应的编码，其中0表示向左走，1表示向右走。

下面是C++的实现代码：

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

using namespace std;

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

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

unordered_map<char, string> encode; // 记录每个字符的编码

void buildHuffmanTree(string s) {
    unordered_map<char, int> freq; // 统计每个字符出现的频率
    for (char c : s) {
        freq[c]++;
    }

    priority_queue<TreeNode*, vector<TreeNode*>, compare> pq; // 最小堆
    for (auto& f : freq) {
        pq.push(new TreeNode(f.first, f.second));
    }

    while (pq.size() > 1) {
        TreeNode* left = pq.top();
        pq.pop();
        TreeNode* right = pq.top();
        pq.pop();
        TreeNode* parent = new TreeNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    TreeNode* root = pq.top();
    pq.pop();

    // 遍历哈夫曼树，记录每个叶子节点的编码
    string path;
    function<void(TreeNode*)> dfs = [&](TreeNode* node) {
        if (!node) return;
        if (!node->left && !node->right) {
            encode[node->ch] = path;
            return;
        }
        path.push_back('0');
        dfs(node->left);
        path.pop_back();

        path.push_back('1');
        dfs(node->right);
        path.pop_back();
    };

    dfs(root);
}

int main() {
    string s = "this is a test string";
    buildHuffmanTree(s);

    // 输出每个字符的编码
    for (auto& e : encode) {
        cout << e.first << " : " << e.second << endl;
    }

    return 0;
}

这段代码实现了一个简单的哈夫曼编码算法，统计了字符串中每个字符出现的频率，构建了一棵哈夫曼树，并记录了每个字符对应的编码。其中，我们使用了一个最小堆来维护当前频率最小的两个节点，使用递归的方式遍历哈夫曼树，并记录每个叶子节点的编码。