哈夫曼树

一些定义

给定N个带有权值的叶子节点，构造一棵二叉树，如果该树的带权路径长度最小，那么它是一棵最优二叉树，即哈夫曼树。

• 路径： 在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。
• 路径长度： 在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。
• 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权
• 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。 例如，图 1 中结点 b 的带权路径长度为 $2 * 5 = 10 $
• 树的带权路径长度：为树中所有叶子结点的带权路径长度之和。通常记作 “WPL”。例如图 1 中所示的这颗树的带权路径长度为：$ WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 $

哈夫曼树的构建

1. 初始的时候，各个节点都自称一树，即构成一个单节点森林

   

2. 所有节点放入优先队列，每次取两个权值最小的顶点，构造父节点$value = left.value+right.value$

   • 如果队列为空，那么返回节点，并且这个节点为根节点root。
   • 否则继续加入队列进行排序。重复上述操作，直到队列为空。