C++哈夫曼编码

发表于 2025-01-03 分类于算法阅读次数：本文字数： 5.8k 阅读时长 ≈ 5 分钟

📚 哈夫曼编码（Huffman Coding）详解

1. 什么是哈夫曼编码？

哈夫曼编码（Huffman Coding） 是一种广泛使用的数据压缩算法，用于减少数据传输和存储所需的空间。它属于一种前缀编码（Prefix Code），即任意一个字符的编码都不会是另一个字符编码的前缀，避免了解码歧义。

1.1 应用场景

文件压缩（例如 ZIP、GZIP 等）
图像压缩（例如 JPEG）
网络通信传输数据

1.2 基本思想

频率（或权重）越高的字符使用的编码越短，频率越低的字符使用的编码越长。
使用二叉树构建编码，频率较小的字符处于树的底部，频率较大的字符靠近根节点。

2. 哈夫曼编码的核心步骤

统计字符频率
- 统计每个字符在数据中的出现次数。
构建哈夫曼树
- 将每个字符作为一个叶子节点，频率作为节点权重。
- 取出频率最小的两个节点，合并成一个新的节点，新的节点的频率是两者之和。
- 重复此过程，直到所有节点合并成一棵树。
生成编码
- 从根节点开始，左子树编码为 0，右子树编码为 1。
- 遍历整棵树，为每个字符生成对应的二进制编码。
编码与解码
- 使用生成的二进制编码进行数据压缩。
- 解码时，使用哈夫曼树进行还原。

3. 哈夫曼编码示例

步骤解析

3.1. 合并节点的核心思想

每次选择频率最小的两个节点
- 将这两个节点作为新节点的左右子节点。
- 新节点的频率是这两个节点的频率之和。
将新节点加入到集合中
- 将合并后的新节点重新加入到节点集合中，继续进行下一轮合并。
重复以上步骤，直到只剩下一个节点
- 最终，所有节点将合并成一棵哈夫曼树。
- 根节点的频率是所有字符频率的总和。

3.2. 详细示例解析

示例数据

假设有以下字符及其频率：

字符	频率
a	5
b	9
c	12
d	13
e	16
f	45

3.2.1 第一步：将每个字符作为独立节点

a(5), b(9), c(12), d(13), e(16), f(45)

3.2.2 第二步：选择频率最小的两个节点进行合并

选择 a(5) 和 b(9)，合并成新节点，频率为 5 + 9 = 14。

  (a+b)(14)
  /      \
a(5)    b(9)

将新节点 (a+b)(14) 加回节点集合：

(a+b)(14), c(12), d(13), e(16), f(45)

3.2.3 第三步：再次选择频率最小的两个节点

选择 c(12) 和 d(13)，合并成新节点，频率为 12 + 13 = 25。

  (c+d)(25)
  /      \
c(12)   d(13)

将新节点 (c+d)(25) 加回节点集合：

(a+b)(14), (c+d)(25), e(16), f(45)

3.2.4 第四步：继续选择频率最小的两个节点

选择 (a+b)(14) 和 e(16)，合并成新节点，频率为 14 + 16 = 30。

      ((a+b)+e)(30)
      /       \
  (a+b)(14)   e(16)
  /     \
a(5)   b(9)

将新节点 (a+b+e)(30) 加回节点集合：

(c+d)(25), ((a+b)+e)(30), f(45)

3.2.5 第五步：合并剩下的两个最小节点

选择 (c+d)(25) 和 ((a+b)+e)(30)，合并成新节点，频率为 25 + 30 = 55。

      ((c+d)+((a+b)+e))(55)
      /                \
  (c+d)(25)        ((a+b)+e)(30)
  /     \           /       \
c(12)  d(13)   (a+b)(14)   e(16)
                    /  \
                  a(5) b(9)

将新节点加入集合：

((c+d)+((a+b)+e))(55), f(45)

3.2.6 第六步：合并最后两个节点

合并 f(45) 和 ((c+d)+((a+b)+e))(55)，频率为 45 + 55 = 100。

   ROOT(100)
   /       \
f(45)   ((c+d)+((a+b)+e))(55)
           /                \
       (c+d)(25)       ((a+b)+e)(30)
       /     \           /       \
     c(12)  d(13)   (a+b)(14)   e(16)
                         /  \
                       a(5) b(9)

3.3. 生成哈夫曼编码

3.3.1 编码规则

向左走，编码为 0
向右走，编码为 1

3.3.2 编码生成

f → 0
c → 100
d → 101
a → 1100
b → 1101
e → 111

3.4. 合并节点的贪心思想

为什么每次选择最小的两个节点合并？

减少树的高度
- 频率小的节点放在树的底层，减少高频字符的路径长度。
保证整体编码长度最小
- 频率越高的字符路径越短，减少整体编码的长度。
贪心选择局部最优解
- 每次选择最小的两个节点合并，最终得到整体最优的哈夫曼树。

3.5. 代码回顾

核心逻辑（合并节点部分）

while (minHeap.size() > 1) {
    HuffmanNode* left = minHeap.top(); minHeap.pop();
    HuffmanNode* right = minHeap.top(); minHeap.pop();

    // 合并两个最小频率节点
    HuffmanNode* newNode = new HuffmanNode('$', left->freq + right->freq);
    newNode->left = left;
    newNode->right = right;

    // 将新节点加入小顶堆
    minHeap.push(newNode);
}

每次取出两个最小节点。
合并为新节点，新的频率是两者之和。
将新节点重新插入到小顶堆中。

3.6. 总结

每次合并最小的两个节点，确保局部最优。
重复合并，直到构建出一棵完整的哈夫曼树。
使用二叉树的左 0 右 1 规则生成编码。
小顶堆保证每次能够快速找到最小的两个节点。

4. 哈夫曼编码 C++ 实现

4.1 代码示例

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

using namespace std;

// 定义哈夫曼树的节点
struct HuffmanNode {
    char data;        // 字符
    int freq;         // 频率
    HuffmanNode *left, *right;

    HuffmanNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};

// 比较函数，用于优先队列
struct Compare {
    bool operator()(HuffmanNode* l, HuffmanNode* r) {
        return l->freq > r->freq; // 小顶堆
    }
};

// 递归打印哈夫曼编码
void printCodes(HuffmanNode* root, string code) {
    if (!root) return;

    // 如果是叶子节点，打印字符和对应编码
    if (root->data != '$') {
        cout << root->data << ": " << code << endl;
    }

    printCodes(root->left, code + "0");
    printCodes(root->right, code + "1");
}

// 哈夫曼编码主函数
void HuffmanCoding(vector<pair<char, int>> freqTable) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;

    // 将字符和频率加入最小堆
    for (auto& pair : freqTable) {
        minHeap.push(new HuffmanNode(pair.first, pair.second));
    }

    // 构建哈夫曼树
    while (minHeap.size() != 1) {
        HuffmanNode* left = minHeap.top(); minHeap.pop();
        HuffmanNode* right = minHeap.top(); minHeap.pop();

        // 创建一个新节点，将左右子节点合并
        HuffmanNode* newNode = new HuffmanNode('$', left->freq + right->freq);
        newNode->left = left;
        newNode->right = right;

        minHeap.push(newNode);
    }

    // 打印哈夫曼编码
    printCodes(minHeap.top(), "");
}

// 主函数
int main() {
    vector<pair<char, int>> freqTable = {
        {'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}
    };

    HuffmanCoding(freqTable);
    return 0;
}

4.2 代码解析

定义节点结构体
- 每个节点包含字符、频率、左右子节点指针。
使用优先队列（小顶堆）
- 频率小的节点优先出队。
构建哈夫曼树
- 每次合并两个频率最小的节点，形成新节点并重新加入堆中。
生成编码
- 使用递归遍历生成每个字符的编码。
打印编码
- 对叶子节点进行编码输出。

4.3 示例输出

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

5. 哈夫曼编码的优缺点

✅ 优点

高效的压缩算法。
适用于字符频率分布不均匀的场景。
前缀编码，无解码歧义。

❌ 缺点

频率统计可能较耗时。
对于字符频率相对均匀的数据，压缩效果不显著。
在动态数据流中编码效率较低。

6. 总结

哈夫曼编码是一种贪心算法，在每一步都选择频率最小的节点进行合并。
构建哈夫曼树的核心是小顶堆，以确保频率最小的节点被优先处理。
哈夫曼编码是一种无前缀编码，有效避免了编码歧义。

通过这个示例和讲解，相信你已经对哈夫曼编码有了清晰的理解！🚀

📚 注：小顶堆（Min Heap）详解

1. 什么是小顶堆？

小顶堆（Min Heap） 是一种二叉堆（Binary Heap），它满足以下两个特性：

完全二叉树：
- 小顶堆必须是一棵完全二叉树，即每一层都被完全填满，除了最后一层可以不满，但节点必须从左到右连续排列。
堆序性（堆性质）：
- 根节点的值小于或等于其所有子节点的值。
- 对于每一个节点 ( i )：
```
A[i] <= A[2i+1] // (左子节点)
A[i] <= A[2i+2] // (右子节点)
```

2. 小顶堆的关键特性

根节点
- 堆顶（根节点）总是存储最小的元素。
插入操作
- 新元素插入到堆的末尾，然后进行上浮操作，以确保堆的性质保持不变。
删除操作
- 通常删除根节点（最小值）。
- 用堆的最后一个节点替换根节点，然后进行下沉操作，以重新维持堆的性质。
优先队列
- 小顶堆常用于实现优先队列（Priority Queue），保证每次出队的都是当前最小的元素。

3. 小顶堆与大顶堆的区别

特性	小顶堆 (Min Heap)	大顶堆 (Max Heap)
根节点	最小值	最大值
子节点	子节点值 >= 根节点值	子节点值 <= 根节点值
应用场景	哈夫曼编码、最短路径算法	堆排序、最大值查找

4. C++ 中的优先队列与小顶堆

4.1 `std::priority_queue`

在 C++ 中，默认的 std::priority_queue 是大顶堆，即最大值优先。

要实现小顶堆，可以使用以下两种方式：

自定义比较器
使用 std::greater 函数对象

4.2 小顶堆示例

示例 1：使用 `std::greater` 实现小顶堆

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // 使用 greater<int> 实现小顶堆
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 插入元素
    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(20);
    minHeap.push(1);

    // 取出最小元素
    cout << "小顶堆的元素出队顺序：";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;

    return 0;
}

✅ 输出：

小顶堆的元素出队顺序：1 5 10 20

示例 2：使用自定义比较器

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 自定义比较器
struct Compare {
    bool operator()(int a, int b) {
        return a > b; // a 大于 b 时，a 排在后面
    }
};

int main() {
    priority_queue<int, vector<int>, Compare> minHeap;

    minHeap.push(15);
    minHeap.push(3);
    minHeap.push(8);
    minHeap.push(1);

    cout << "小顶堆的元素出队顺序：";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;

    return 0;
}

✅ 输出：

小顶堆的元素出队顺序：1 3 8 15

5. 小顶堆的应用场景

哈夫曼编码
- 使用小顶堆确保每次选择权重最小的两个节点进行合并。
Dijkstra 算法
- 寻找最短路径时，使用小顶堆优先选择当前路径最短的节点。
Top K 问题
- 在大量数据中快速找到前 K 小的元素。
事件驱动仿真
- 模拟器中按照事件发生的时间顺序处理事件。

6. 总结

小顶堆是一种完全二叉树，每个父节点的值都小于或等于其子节点的值。
在 C++ 中，可以使用 std::priority_queue 配合 std::greater 或自定义比较器来实现小顶堆。
小顶堆的核心操作包括插入（上浮）、删除（下沉）。
主要应用于优先队列、哈夫曼编码、Dijkstra 算法等场景。

📚 哈夫曼编码（Huffman Coding）详解

1. 什么是哈夫曼编码？

1.1 应用场景

1.2 基本思想

2. 哈夫曼编码的核心步骤

3. 哈夫曼编码示例

步骤解析

3.1. 合并节点的核心思想

3.2. 详细示例解析

示例数据

3.2.1 第一步：将每个字符作为独立节点

3.2.2 第二步：选择频率最小的两个节点进行合并

3.2.3 第三步：再次选择频率最小的两个节点

3.2.4 第四步：继续选择频率最小的两个节点

3.2.5 第五步：合并剩下的两个最小节点

3.2.6 第六步：合并最后两个节点

3.3. 生成哈夫曼编码

3.3.1 编码规则

3.3.2 编码生成

3.4. 合并节点的贪心思想

为什么每次选择最小的两个节点合并？

3.5. 代码回顾

核心逻辑（合并节点部分）

3.6. 总结

4. 哈夫曼编码 C++ 实现

4.1 代码示例

4.2 代码解析

4.3 示例输出

5. 哈夫曼编码的优缺点

✅ 优点

❌ 缺点

6. 总结

📚 注：小顶堆（Min Heap）详解

1. 什么是小顶堆？

2. 小顶堆的关键特性

3. 小顶堆与大顶堆的区别

4. C++ 中的优先队列与小顶堆

4.1 std::priority_queue

4.2 小顶堆示例

示例 1：使用 std::greater 实现小顶堆

示例 2：使用自定义比较器

5. 小顶堆的应用场景

6. 总结

4.1 `std::priority_queue`

示例 1：使用 `std::greater` 实现小顶堆