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

霍夫曼编码是一种常用的数据压缩算法，它通过将出现频率较高的字符用较短的编码表示，从而实现对数据的高效压缩。贪心算法是霍夫曼编码的核心思想之一。

在C++中实现霍夫曼编码的贪心算法，可以按照以下步骤进行：

1. 创建一个结构体或类来表示霍夫曼树的节点，包含字符、字符出现的频率以及左右子节点等信息。

2. 统计给定文本中每个字符出现的频率，并根据频率构建一个最小堆（优先队列），以频率作为比较的依据。

3. 从最小堆中选择两个频率最低的节点，将它们合并为一个新节点，并将新节点插入到最小堆中。

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

5. 遍历霍夫曼树，给每个字符赋予对应的编码。左子节点为0，右子节点为1。

6. 使用生成的霍夫曼编码对原始文本进行压缩。

下面是一个简单的C++代码示例，实现了霍夫曼编码的贪心算法：

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

struct HuffmanNode {
    char data;
    int freq;
    HuffmanNode* left;
    HuffmanNode* right;
};

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

HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;
    
    for (auto& pair : freqMap) {
        HuffmanNode* node = new HuffmanNode();
        node->data = pair.first;
        node->freq = pair.second;
        node->left = nullptr;
        node->right = nullptr;
        minHeap.push(node);
    }
    
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        
        HuffmanNode* right = minHeap.top();
        minHeap.pop();
        
        HuffmanNode* newNode = new HuffmanNode();
        newNode->data = '\0';
        newNode->freq = left->freq + right->freq;
        newNode->left = left;
        newNode->right = right;
        
        minHeap.push(newNode);
    }
    
    return minHeap.top();
}

void generateHuffmanCodes(HuffmanNode* root, string code, unordered_map<char, string>& codes) {
    if (root == nullptr) {
        return;
    }
    
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->data] = code;
    }
    
    generateHuffmanCodes(root->left, code + "0", codes);
    generateHuffmanCodes(root->right, code + "1", codes);
}

string compressText(string text, unordered_map<char, string>& codes) {
    string compressedText = "";
    
    for (char c : text) {
        compressedText += codes[c];
    }
    
    return compressedText;
}

int main() {
    string text = "Hello, World!";
    
    unordered_map<char, int> freqMap;
    for (char c : text) {
        freqMap[c]++;
    }
    
    HuffmanNode* root = buildHuffmanTree(freqMap);
    
    unordered_map<char, string> codes;
    generateHuffmanCodes(root, "", codes);
    
    string compressedText = compressText(text, codes);
    
    cout << "Compressed Text: " << compressedText << endl;
    
    return 0;
}