一、Huffman 树 / Huffman 编码 1. 前提条件 Huffman 树本质是： 贪心 + 二叉树 + 小根堆 它解决的是： 如何让编码总长度最短 常见场景： 数据压缩 字符编码 最优二叉树 2. 核心概念 假设字符出现频率： A: 5 B: 9 C: 12 D: 13 E: 16 F: 45 出现次数越多的字符，应该编码越短。 出现次数越少的字符，编码可以长一点。 所以 Huffman 的核心贪心策略是： 每次选权值最小的两棵树合并 3. WPL 是什么 WPL：带权路径长度 计算方式：WPL = 所有叶子结点的 权值 × 深度 之和 例如：A 权值 5，深度 3 贡献 = 5 × 3 = 15 Huffman 树就是让： WPL 最小的二叉树。 4. 构造过程 权值： 5, 9, 12, 13, 16, 45 每次取最小两个合并。 第一步： 5 + 9 = 14 现在： 12, 13, 14, 16, 45 第二步： 12 + 13 = 25 现在： 14, 16, 25, 45 第三步： 14 + 16 = 30 现在： 25, 30, 45 第四步： 25 + 30 = 55 现在： 45, 55 第五步： 45 + 55 = 100 结束。 所以总代价 WPL 可以在合并时直接累加： 14 + 25 + 30 + 55 + 100 = 224 5. 为什么可以累加合并值 每次合并两个结点，相当于这两个子树所有叶子的深度都 +1。 所以新增的 WPL 正好是： 左子树总权值 + 右子树总权值 也就是合并后的权值。 ---补充一下我对于此的理解：Huffman算法维护的不是一棵树，而是一片森林（Forest）。 开始例如： 权值： 5 7 10 15 此时：根本没有树。 只有： 5 7 10 15 每一个叶子：就是一棵树。（每个叶子都计算过自己的权重） 所以：开始有 n 棵树 结束只剩 1 棵树 整个算法就是：不断把两棵树合并。 为什么用小根堆？ 因为每一步都要找：森林里面权值最小的两棵树 例如： 森林： 5 7 10 15 最小：5和7 所以最适合的数据结构：小根堆 小根堆维护的是：森林 不是二叉树。 --- HuffmanNode到底是什么？ struct HuffmanNode { int weight; struct HuffmanNode* left; struct HuffmanNode* right; }; 这里不是堆 而是：一棵树的根节点。 例如开始： A weight=5 就是： A 后来： 变成： 12 / \ 5 7 那么整个：12 就是： HuffmanNode* 以后：放进堆。 所以： 堆里面放的是：树根指针。 ----为什么比较weight？ 因为： 例如： 22 / \ 10 12 / \ 5 7 对于小根堆来说。 它根本不关心： 里面长什么样。 它只关心：整棵树总权值22 所以： 比较： node->weight即可。 left right 完全不用比较。 因为：left/right 只是保存树结构。 --- 一个完整例子 开始权值： 5 7 10 15 森林： 5 7 10 15 放入小根堆： Heap ↓ 5 7 10 15 第一步： pop： 5 7 建立： 12 / \ 5 7 放回堆： Heap ↓ 10 12(树) 15 注意： 这里： Heap里面： 已经不是： 5 7 而是： 12 / \ 5 7 这一整棵树。 第二步： 取： 10 12 建立： 22 / \ 10 12 / \ 5 7 放回： Heap： 15 22(树) 第三步： 取： 15 22 建立： 37 / \ 15 22 / \ 10 12 / \ 5 7 结束。 森林： 只剩：一棵树 这就是： Huffman树。 ---- 小根堆为什么存树？ 真正内存里面： 其实是： Heap ↓ data[0] ↓ Tree Root ↓ 整棵树 所以： Heap 不是存树 而是存树根指针。 例如： data[0] ↓ 22 因为： 22 知道left 知道right 所以： 整个树： 都找得到。 ----为什么swapNode是二级指针？ 例如： Heap： data[0] ↓ 22 data[1] ↓ 15 交换的是： 两个树根指针 所以： swapNode( &heap->data[0], &heap->data[1] ); 参数： 就是： HuffmanNode** 不是： HuffmanNode* 这一点和我们之前哈希那里讲的： 交换指针 必须传地址 完全一样。 把 Huffman 想成： 维护一片森林 ↓ 小根堆维护这些树 ↓ 每次挑两棵最轻的树 ↓ 合成一棵更大的树 ↓ 放回森林 ↓ 直到森林只剩最后一棵树 因此： Huffman 的 WPL = 每次合并权值之和 6. Huffman 树结点结构 struct HuffmanNode { int weight; struct HuffmanNode* left; struct HuffmanNode* right; }; 含义： weight：权值 left：左孩子 right：右孩子 叶子结点就是原始字符。 内部结点是合并出来的。 7. 小根堆实现 Huffman 每次都要取两个最小值。 所以最适合用：小根堆 我们先写一个存 struct HuffmanNode* 的小根堆。 7.1 堆结构 #include #define MAXN 1000 struct HuffmanNode { int weight; struct HuffmanNode* left; struct HuffmanNode* right; }; struct MinHeap { struct HuffmanNode* data[MAXN]; int size; }; 7.2 创建结点 struct HuffmanNode* createNode(int weight) { struct HuffmanNode* node = malloc(sizeof(struct HuffmanNode)); node->weight = weight; node->left = NULL; node->right = NULL; return node; } 7.3 交换堆元素 void swapNode(struct HuffmanNode** a, struct HuffmanNode** b) { struct HuffmanNode* temp = *a; *a = *b; *b = temp; } 注意这里是： struct HuffmanNode** 因为堆数组里存的是： struct HuffmanNode* 交换两个指针，就要传指针的地址。 7.4 push 上滤 void push(struct MinHeap* heap, struct HuffmanNode* node) { int i = heap->size; heap->data[i] = node; heap->size++; while(i > 0) { int parent = (i - 1) / 2; if(heap->data[parent]->weight <= heap->data[i]->weight) { break; } swapNode(&heap->data[parent], &heap->data[i]); i = parent; } } 意思：新结点先放到堆尾 如果比父节点小，就往上换 7.5 pop 取出最小值 struct HuffmanNode* pop(struct MinHeap* heap) { if(heap->size == 0) { return NULL; } struct HuffmanNode* ans = heap->data[0]; heap->data[0] = heap->data[heap->size - 1]; heap->size--; int i = 0; while(1) { int left = 2 * i + 1; int right = 2 * i + 2; int smallest = i; if(left < heap->size && heap->data[left]->weight < heap->data[smallest]->weight) { smallest = left; } if(right < heap->size && heap->data[right]->weight < heap->data[smallest]->weight) { smallest = right; } if(smallest == i) { break; } swapNode(&heap->data[i], &heap->data[smallest]); i = smallest; } return ans; } 意思： 堆顶最小 删除堆顶后，把最后一个元素放堆顶 再下滤恢复小根堆 8. 构造 Huffman 树 struct HuffmanNode* buildHuffmanTree(int weights[], int n) { struct MinHeap heap; heap.size = 0; for(int i = 0; i < n; i++) { push(&heap, createNode(weights[i])); } while(heap.size > 1) { struct HuffmanNode* left = pop(&heap); struct HuffmanNode* right = pop(&heap); struct HuffmanNode* parent = createNode(left->weight + right->weight); parent->left = left; parent->right = right; push(&heap, parent); } return pop(&heap); } 代码理解 先把所有权值放进小根堆： 5, 9, 12, 13, 16, 45 每次： left = pop(&heap); right = pop(&heap); 取两个最小。 然后： parent = createNode(left->weight + right->weight); 合成新树。 再： push(&heap, parent); 放回堆。 直到堆里只剩一棵树。 这棵树就是 Huffman 树。 9. 只求 WPL 的话就建堆之后两两都加起来求和就行 int huffmanWPL(int weights[], int n) { struct MinHeap heap; heap.size = 0; for(int i = 0; i < n; i++) { push(&heap, createNode(weights[i])); } int wpl = 0; while(heap.size > 1) { struct HuffmanNode* a = pop(&heap); struct HuffmanNode* b = pop(&heap); int sum = a->weight + b->weight; wpl += sum; push(&heap, createNode(sum)); } return wpl; } 例子： 5,9,12,13,16,45 返回：224 10. Huffman 编码 建好树以后： 左边记 0 右边记 1 从根到叶子的路径，就是该字符编码。 例如： 向左，向右，向左 编码就是 010 注意： Huffman 编码不是唯一的 因为左右孩子可以互换。 但： WPL 是一样的 11. Huffman 易错点 1. 每次取两个最小，不是取一个最小。 2. Huffman 树没有度为 1 的结点。 只有叶子结点和度为 2 的结点。 3. n 个叶子结点的 Huffman 树，总结点数是 2n - 1。 4. Huffman 编码不唯一，但 WPL 最小值唯一。 5. 只求 WPL 时，可以不用真正建树，直接累加每次合并值。 12. Huffman 总结 Huffman 树 核心： 每次取两个最小权值合并 目标： WPL 最小 WPL： 权值 × 深度 之和 构造： 所有权值入小根堆 每次弹出两个最小 合并成新结点 再放回堆 编码： 左0右1 根到叶子的路径就是编码 重要性质： n 个叶子 总结点数 2n-1 没有度为1的结点