Huffman算法

介绍

求解最优二叉树问题通常使用动态规划算法中的一种称为"Huffman算法"或者"Huffman编码"。

Huffman算法的基本思想：

根据节点的频率或者权重构建一棵最优二叉树。最小频率的节点会被放置在树的底部，而较大频率的节点则放置在较高的位置，以此最大限度地减少树的平均路径长度。

具体步骤如下：
1. 首先，统计所有节点的频率或者权重，并按照频率或者权重对节点进行排序。
2. 创建一个包含所有节点的森林（由单个节点组成的树）。
3. 从森林中选择两个具有最小频率或者权重的节点，并创建一个新的父节点，频率或者权重等于这两个节点的频率或者权重之和。
4. 将这两个节点作为新节点的左右子节点，并将新节点加入到森林中。
5. 重复步骤3和步骤4，直到森林中只剩下一个节点，即最优二叉树的根节点。
6. 最后，对最优二叉树进行编码，将频率或者权重较大的节点赋予较短的编码，而频率或者权重较小的节点赋予较长的编码。

Huffman算法的时间复杂度主要取决于对节点进行排序的部分，通常使用的排序算法是堆排序或者快速排序，时间复杂度为O(nlogn)，其中n为节点的数量。

总结一下，Huffman算法是一种用于构建最优二叉树的动态规划算法，它通过选择频率或者权重最小的节点来构建树，以最小化树的平均路径长度。

举例

#include 
#include 
#include 
using namespace std;
 
// Huffman树节点
struct HuffmanNode {
    char data;                  // 符号（字符）
    int frequency;              // 频率
    HuffmanNode* left;
    HuffmanNode* right;
 
    HuffmanNode(char d, int freq) : data(d), frequency(freq), left(nullptr), right(nullptr) {}
};
 
// 比较函数（按照频率从小到大排序）
struct Compare {
    bool operator()(const HuffmanNode* a, const HuffmanNode* b) {
        return a->frequency > b->frequency;
    }
};
 
// 构建Huffman树
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& freqMap) {
    // 创建小顶堆，用于选择频率最小的节点
    priority_queue, Compare> minHeap;
 
    // 创建叶子节点，并将其加入到小顶堆中
    for (const auto& entry : freqMap) {
        HuffmanNode* node = new HuffmanNode(entry.first, entry.second);
        minHeap.push(node);
    }
 
    // 构建Huffman树（合并节点）
    while (minHeap.size() > 1) {
        // 选择频率最小的两个节点
        HuffmanNode* leftNode = minHeap.top();
        minHeap.pop();
        HuffmanNode* rightNode = minHeap.top();
        minHeap.pop();
 
        // 创建新节点，频率为子节点频率之和
        HuffmanNode* newNode = new HuffmanNode('$', leftNode->frequency + rightNode->frequency);
        newNode->left = leftNode;
        newNode->right = rightNode;
 
        // 将新节点加入到小顶堆中
        minHeap.push(newNode);
    }
 
    // 返回Huffman树的根节点
    return minHeap.top();
}
 
// 生成Huffman编码
void generateHuffmanCodes(HuffmanNode* root, string code, unordered_map<char, string>& huffmanCodes) {
    if (root == nullptr) {
        return;
    }
 
    // 叶子节点表示一个字符，将其编码加入到map中
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCodes[root->data] = code;
    }
 
    // 递归生成左子树和右子树的编码
    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}
 
// 压缩数据
string compressData(const string& data, const unordered_map<char, string>& huffmanCodes) {
    string compressedData = "";
 
    // 遍历原始数据，将字符替换为对应的Huffman编码
    for (char c : data) {
        compressedData += huffmanCodes.at(c);
    }
 
    return compressedData;
}
 
// 解压缩数据
string decompressData(const string& compressedData, HuffmanNode* root) {
    string decompressedData = "";
    HuffmanNode* current = root;
 
    // 遍历压缩后的数据，根据Huffman编码逐个恢复原始字符
    for (char c : compressedData) {
        if (c == '0') {
            current = current->left;
        } else {
            current = current->right;
        }
 
        // 到达叶子节点，表示找到一个字符
        if (current->left == nullptr && current->right == nullptr) {
            decompressedData += current->data;
            current = root;  // 恢复到根节点以继续下一个字符的解压缩
        }
    }
 
    return decompressedData;
}
 
int main() {
    string data = "hello huffman!";
    unordered_map<char, int> freqMap;
 
    // 统计字符频率
    for (char c : data) {
        freqMap[c]++;  // 字符已存在，则自增; 否则, 创建新键值对
    }
 
    // 构建Huffman树
    HuffmanNode* root = buildHuffmanTree(freqMap);
 
    // 生成Huffman编码
    unordered_map<char, string> huffmanCodes;
    generateHuffmanCodes(root, "", huffmanCodes);
    
    // 输出Huffman编码
    cout << "Huffman Codes:" << endl;