已知权值求哈夫曼树

哈夫曼树是一种对于给定的权值序列构造出来的二叉树，它的带权路径长度最小。那么如果我们已知一个权值序列，怎样才能有效地求出它的哈夫曼树呢？本文将从多个角度来分析这个问题。

第一种方法：贪心算法

哈夫曼树的构建需要满足「带权路径长度最小」的条件，我们可以采用贪心的思想，在每一步中选择「较小的两个权值」进行合并，这样一定可以保证最终得到的哈夫曼树的带权路径长度最小。

所谓「较小的两个权值」，就是指当前权值集合中权值最小的两个。因此，我们可以先将权值集合按照从小到大的顺序排列，然后每次选取前两个最小的组成一棵新的子树，直到最终构建出来的哈夫曼树。

虽然贪心算法的时间复杂度为 O(nlogn)，但是其明显是最优解，无论是时间效率还是空间效率都是瓶颈所在。

第二种方法：优先队列

优先队列是一种经典的数据结构，它可以用来存储一个集合并保证在任何时候都可以访问最大或最小的那个元素。在哈夫曼树的构建过程中，我们可以利用优先队列来简化代码。具体过程如下：

1. 将每个权值作为一个节点，将这些节点放入一个优先队列中；

2. 每次从优先队列中选取两个权值最小的节点进行合并，合并后的节点作为新的子树放回优先队列；

3. 重复上述过程，直到优先队列中只剩下一个节点，此时得到的节点即为根节点，构建出来的二叉树即为哈夫曼树。

优先队列相对于第一种方法的想法更简单，容易实现，时间复杂度为 O(nlogn)，但是其空间效率相对差一些，因为需要额外使用一个优先队列来存储节点。

第三种方法：动态规划

动态规划也可以用来求解哈夫曼树。具体做法是：

1. 设 W 为待构建的哈夫曼树的结点集合，w1-wi为权值集合，用 c(l,i) 表示 w1-wi 构成的哈夫曼树的带权路径长度；

2. 显然，c(l,i) 的值是通过取 w1-wi 中某两个权值的和进行求解的，因此，我们可以先枚举一组取法，然后将问题分解为更小的子问题；

3. 设 wj 和 wk 为 w1-wi 中最小的两个值，c(l,i) 可以表示为：C(l,i) = C(l, k-1) + C(k+1, i) + wj + wk；

4. 重复上述过程，直到得到最终的 C(1,n) 即为构建出来的哈夫曼树。

动态规划的时间复杂度为 O(n^3)，比前两种方法慢，但有些时候它在实现上更加容易。