有 n 堆果子，每堆果子的质量已知，现在需要把这些果子合并成一堆，但是每次只能把两堆果子合并到一起，同时会消耗与两堆果子质量之和等值的体力。

　　为了尽可能节省体力，请设计出合并的次序方案，使得耗费的体力最少，并给出消耗的体力值。

　　例如有 3 堆果子，质量依次为1、2、9。那么可以先将质量为 1 和 2 的果堆合并，新堆质量为 3 ，因此耗费体力为 3 。

　　接着，将新堆与原先的质量为 9 的果堆合并，又得到新的堆，质量为 12 ，因此耗费体力为 12 。

　　为了解决这个问题，不妨进行如下考虑：把每堆果子都看作结点，果堆的质量视作结点的权值，这样合并两个果堆的过程就可以视作给它们生成一个父结点，且父结点的权值等于它们的质量之和，于是把 n 堆果子合并成一堆的过程可以用一棵树来表示。下图是将5堆质量分别为 1、2、2、3、6 的果子进行合并的某一种方案，可以发现初始的果堆一定处于叶子结点（想一想为什么？），而非叶子结点都是合并过程中新生成的结点。

　　事实上可以发现，消耗体力之和也可以通过把叶子结点的权值乘以它们各自的路径长度再求和来获得，其中叶子结点的路径长度是指从根结点出发到达该结点所经过的边数。

　　例如上面的例子中，从根结点到达权值为 6 的叶子结点的路径长度为 2，而从根结点到达权值为 1 的叶子结点的路径长度为 3，于是 32 可以通过 2*2+6*2＋1*3＋3*3＋2*2 来计算得到。

　　例如上面的例子中，权值为 6 的叶子结点的带权路径长度为 6*2=12 ，而权值为 1 的叶子结点的带权路径长度为 1*3=3 。

　　另外，树的带权路径长度（Weighted Path Length of Tree，WPL）等于它所有叶子结点的带权路径长度之和。

　　于是合并果子问题就转换成：已知 n 个数，寻找一棵树，使得树的所有叶子结点的权值恰好为这 n 个数，并且使得这棵树的带权路径长度最小。

　　显然，对同一组叶子结点来说，哈夫曼树可以是不唯一的，但是最小带权路径长度一定是唯一的（想一想为什么？）。

　　1、初始状态下共有 n 个结点（结点的权值分别是给定的 n 个数），将它们视作 n 棵只有一个结点的树。

　　2、合并其中根结点权值最小的两棵树，生成两棵树根结点的父结点，权值为这两个根结点的权值之和，这样树的数量就减少了一个。

　　以前面的例子为例，初始状态下有 5 个果堆，质量分别为 1、2、2、3、6，当前状态如下图所示。（初始果堆）

　　（1）此时根结点权值最小为 1 和 2 ，将它们合并，得到新的根结点，其权值为 3 （也即新果堆的质量为 3 ）。此过程如下图所示。（合并权值最小的 1 和 2 ）

　　（2）此时根结点权值最小为 2 和 3 （选择 2 和 3 也可以），将它们合并，得到新的根结点，其权值为 5 （也即新果堆的质量为 5 ）。此过程如下图所示。（合并 2 和 3 ）

　　（3）此时根结点权值最小为 3 和 5 ，将它们合并，得到新的根结点，其权值为 8 （也即新果堆的质量为 8 ）。此过程如下图所示。

　　（4）此时根结点权值最小为 6 和 8 ，将它们合并，得到新的根结点，其权值为 14（也即新果堆的质量为 14）。于是只剩下一棵树，算法结束，得到的就是哈夫曼树，可计算得其带权路径长度为 30，也即合并果子需要消耗的最小体力为 30。得到的哈夫曼树如下图所示。

　　通过这个例子也可以发现，对哈夫曼树来说不存在度为 1 的结点，并且权值越高的结点相对来说越接近根结点。

　　至此，大家应当对哈夫曼树的构建有一个直观的理解，关于算法的正确性可以参考算法导论。

　　而在很多实际场景中，不需要真的去构建一棵哈夫曼树，只需要能得到最终的带权路径长度即可（例如合并果子问题就只需要知道消耗的最小体力），因此大家需要着重掌握的是哈夫曼树的构建思想，也就是反复选择两个最小的元素，合并，直到只剩下一个元素。

　　以合并果子问题为例，初始状态下将果堆的质量压入优先队列（注意含义为小顶堆），之后每次从优先队列顶部取出两个最小的数，将它们相加并重新压入优先队列（需要在外部定义一个变量 ans，将相加的结果累加起来），重复直到优先队列中只剩下一个数，此时就得到了消耗的最小体力 ans，并且方案也可以在这个过程中得到。米乐 M6米乐 M6