哈夫曼编码贪心算法贪在哪

哈夫曼编码（Huffman Coding），也称为最优二叉树编码或霍夫曼树编码，是一种无损数据压缩方法。其算法是基于贪心策略实现的，主要“贪”在两个关键步骤：

1. **构建哈夫曼树**: 在这个阶段，算法贪心地选择频率最低的字符作为新节点，合并频率最高的两个字符节点形成一个新的节点，这个新节点的频率是两个子节点频率之和。这个过程重复，直到所有字符都被合并成一棵完全二叉树。

2. **生成编码**: 在哈夫曼树生成后，算法会从根节点开始，自底向上为每个字符分配一个编码。叶子节点（原始字符）的编码是它到根节点的路径上'0'和'1'的序列。这个过程也是贪心的，因为每次都是从当前最小代价节点出发，生成最短的编码。

**相关问题--:**
1. 哈夫曼编码如何根据字符频率构建树？
2. 为什么说哈夫曼编码是贪心的，它如何实现最优编码？
3. 除了数据压缩，哈夫曼编码还有哪些应用场景？

相关问题

哈夫曼编码 贪心算法

哈夫曼编码是一种基于贪心算法的压缩算法，它通过将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，从而达到压缩数据的目的。哈夫曼编码的实现需要建立哈夫曼树，而建立哈夫曼树的过程也是基于贪心算法的。在建立哈夫曼树的过程中，需要先将所有的字符按照出现频率从小到大排序，然后每次选取出现频率最小的两个字符，将它们合并成一个新的节点，并将它们的出现频率相加作为新节点的权值，最终得到一棵哈夫曼树。在哈夫曼树中，每个字符的编码就是从根节点到该字符所在节点的路径上的所有边的方向所组成的二进制数，而每个字符的编码都是唯一的。因此，哈夫曼编码可以实现无损压缩，即压缩后的数据可以完全还原为原始数据。

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

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

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

// 定义哈夫曼树节点
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;
    }
};

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

// 递归遍历哈夫曼树，生成编码表
void generateHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
    if (!root) {
        return;
    }
    if (root->ch != '$') {
        codeMap[root->ch] = code;
    }
    generateHuffmanCode(root->left, code + "0", codeMap);
    generateHuffmanCode(root->right, code + "1", codeMap);
}

// 哈夫曼编码
string huffmanEncode(string s) {
    unordered_map<char, int> freqMap;
    for (char c : s) {
        freqMap[c]++;
    }
    HuffmanNode* root = buildHuffmanTree(freqMap);
    unordered_map<char, string> codeMap;
    generateHuffmanCode(root, "", codeMap);
    string res = "";
    for (char c : s) {
        res += codeMap[c];
    }
    return res;
}

// 哈夫曼解码
string huffmanDecode(string s, HuffmanNode* root) {
    string res = "";
    HuffmanNode* cur = root;
    for (char c : s) {
        if (c == '0') {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
        if (cur->ch != '$') {
            res += cur->ch;
            cur = root;
        }
    }
    return res;
}

// 测试代码
int main() {
    string s = "abacabad";
    string encoded = huffmanEncode(s);
    cout << "Encoded string: " << encoded << endl;
    HuffmanNode* root = buildHuffmanTree({{'a', 2}, {'b', 2}, {'c', 1}, {'d', 1}});
    string decoded = huffmanDecode(encoded, root);
    cout << "Decoded string: " << decoded << endl;
    return 0;
}