Huffman树

一、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 <stdlib.h>

#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 易错点

12. 每次取两个最小，不是取一个最小。

13. Huffman 树没有度为 1 的结点。
    只有叶子结点和度为 2 的结点。

14. n 个叶子结点的 Huffman 树，总结点数是 2n - 1。

15. Huffman 编码不唯一，但 WPL 最小值唯一。

16. 只求 WPL 时，可以不用真正建树，直接累加每次合并值。

17. Huffman 总结

Huffman 树

核心：
每次取两个最小权值合并

目标：
WPL 最小

WPL：
权值 × 深度 之和

构造：
所有权值入小根堆
每次弹出两个最小
合并成新结点
再放回堆

编码：
左0右1
根到叶子的路径就是编码

重要性质：
n 个叶子
总结点数 2n-1
没有度为1的结点