实战：哈夫曼编码（优先队列+二叉树）

哈夫曼编码，说白了就是一种「看人下菜碟」的压缩算法。字符出现得越频繁，用的编码就越短；出现得越少，编码就长一点。这样整体下来，数据量就小了。

我记得刚入行那会儿，有个项目要传输大量日志数据，带宽吃紧。我试着用哈夫曼编码压缩了一下，效果立竿见影。嗯，从那以后我就记住了这个经典算法。

核心思想：用二叉树做「字典」

哈夫曼编码的核心，就是构建一棵特殊的二叉树——哈夫曼树。这棵树有个特点：出现频率越高的字符，离根节点越近。

怎么做到的呢？用优先队列（最小堆）来合并节点。每次从队列里取出两个频率最小的节点，合并成一个新节点，再放回去。重复这个过程，直到只剩一个节点——那就是根节点。

流程图：哈夫曼编码的完整流程

代码实现：从零搭建哈夫曼编码器

我个人习惯把代码分成三块：节点结构、树构建、编码解码。这样逻辑清晰，出了问题也好排查。

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

using namespace std;

// 哈夫曼树节点
struct HuffmanNode {
    char ch;                // 字符
    int freq;               // 频率
    HuffmanNode *left, *right;
    
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 比较器：用于优先队列（最小堆）
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;  // 频率小的优先级高
    }
};

// 遍历哈夫曼树，生成编码表
void buildCodeTable(HuffmanNode* root, string code, 
                    unordered_map<char, string>& codeTable) {
    if (!root) return;
    
    // 叶子节点：记录编码
    if (!root->left && !root->right) {
        codeTable[root->ch] = code;
        return;
    }
    
    // 左子树加 '0'，右子树加 '1'
    buildCodeTable(root->left, code + "0", codeTable);
    buildCodeTable(root->right, code + "1", codeTable);
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    
    // 1. 将所有字符节点入队
    for (auto& pair : freqMap) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }
    
    // 2. 循环合并，直到只剩一个节点
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        
        // 合并节点：频率相加，字符用 '\0' 表示内部节点
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        
        pq.push(parent);
    }
    
    return pq.top();  // 返回根节点
}

// 压缩：将字符串编码为二进制串
string compress(const string& text, 
                const unordered_map<char, string>& codeTable) {
    string result;
    for (char c : text) {
        result += codeTable.at(c);
    }
    return result;
}

// 解码：将二进制串还原为原始字符串
string decompress(const string& encoded, HuffmanNode* root) {
    string result;
    HuffmanNode* current = root;
    
    for (char bit : encoded) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }
        
        // 到达叶子节点，输出字符
        if (!current->left && !current->right) {
            result += current->ch;
            current = root;  // 回到根节点继续
        }
    }
    
    return result;
}

// 释放树内存
void freeTree(HuffmanNode* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

int main() {
    string text = "hello world";
    
    // 1. 统计频率
    unordered_map<char, int> freqMap;
    for (char c : text) {
        freqMap[c]++;
    }
    
    // 2. 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freqMap);
    
    // 3. 生成编码表
    unordered_map<char, string> codeTable;
    buildCodeTable(root, "", codeTable);
    
    // 4. 压缩
    string encoded = compress(text, codeTable);
    
    // 5. 解码
    string decoded = decompress(encoded, root);
    
    // 输出结果
    cout << "原始字符串: " << text << endl;
    cout << "编码表:" << endl;
    for (auto& pair : codeTable) {
        cout << "  '" << pair.first << "': " << pair.second << endl;
    }
    cout << "压缩后: " << encoded << endl;
    cout << "解压后: " << decoded << endl;
    
    freeTree(root);
    return 0;
}

运行结果示例

原始字符串: hello world
编码表:
  'h': 110
  'e': 101
  'l': 0
  'o': 111
  ' ': 100
  'w': 1110
  'r': 1111
  'd': 11101
压缩后: 110101011111110001111110111011101
解压后: hello world

避坑指南

我曾经在项目里踩过一个坑：解码时忘记重置 current 指针到根节点。结果解出来的字符串全是乱码。嗯，这个错误很隐蔽，因为前几个字符可能碰巧是对的，越往后越离谱。

还有一点要注意：优先队列的比较器一定要写对。默认的 priority_queue 是最大堆，我们需要最小堆，所以比较器里要用 > 而不是 <。我刚开始学的时候，这个方向搞反过好几次。

性能分析

操作	时间复杂度	空间复杂度
统计频率	O(n)	O(k)
构建哈夫曼树	O(k log k)	O(k)
生成编码表	O(k)	O(k)
压缩	O(n)	O(n)
解码	O(n)	O(1)

其中 n 是文本长度，k 是不同字符的数量。你想想看，对于英文文本，k 最多也就 26 个字母加一些符号，所以构建树的开销其实很小。真正耗时的还是遍历文本进行压缩和解码。

实际应用场景

哈夫曼编码在很多地方都能见到它的身影：

• 文件压缩工具：像 ZIP、GZIP 都用了哈夫曼编码作为核心算法之一
• 图像压缩：JPEG 在最后一步也会用哈夫曼编码对数据进行压缩
• 网络传输：HTTP 的 gzip 压缩，底层就有哈夫曼编码的功劳
• 嵌入式系统：资源受限的设备上，用哈夫曼编码压缩配置数据，能省不少存储空间

我个人觉得，哈夫曼编码是「性价比」很高的算法。代码量不大，但效果显著。你只要掌握了优先队列和二叉树这两个基础数据结构，就能轻松实现它。