霍夫曼树一例（算法）

霍夫曼树一例（算法）
  -- Huffman-Tree应用一例

---

# Huffman-Tree

（搜集整理哈夫曼树理论知识）
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树又称为最优树。

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。

此算法的思想是：
（1）设给定的一组权值为{W1，W2，W3，……Wn}，据此生成森林F={T1，T2，T3，……Tn},F 中的没棵二叉树只有一个带权为W1的根节点（i=1，2，……n）。
（2）在F中选取两棵根节点的权值最小和次小的二叉树作为左右构造一棵新的二叉树，新二叉树根节点的权值为其左、右子树根节点的权值之和。
（3）在F中删除这两棵最小和次小的二叉树，同时将新生成的二叉树并入森林中。
（4）重复（2）（3）过程直到F中只有一棵二叉树为止。

霍夫曼树

                    

维基百科霍夫曼树

百度百科哈夫曼树

# 问题描述

     （源自于Google groups论坛讨论，转）

问题：把一块长度为L的木棒切成N块，每段的大小必须为a1,a2,…,an，每一次切木棒的代价为当前木棒的长度，完成切割任务的最小代价？

# 测试案例

Input
首先输入T，有T个测试用例
每个测试用例输入两行
第一行整数L和N。接下来一行是N个数表示每一段的木棒长度。
Output
求完成任务的最小代价

Sample Input
2
10 4
1 2 3 4
306 8
120 37 42 42 32 2 7 24
Sample Output
19
785

# 解决方案

霍夫曼树解法的确是一种“美妙”的解决方案啊。

我刚开始看到这问题倒没想到霍夫曼。倒是其他思路，解法一。

> 解法一：

（存在问题）
1 降序排序集合A{a1,a2,…,an} 。

2 遍历集合A，计算每次切木棒代价cost_i。针对前后相同的元素，ai==aj，特殊计算：
     先切出木棒2*a1，再从2*ai木棒对半切分。
 
3 以上切木棒过程，累加不同cost_i，得到cost_sun即所求结果最小代价。

看似OK，跑了几个简单测试用例，包括上面的两个用例，均通过。不过想想觉得不太对劲。
可以猜想知道，对于复杂的测试案例结果就错误了。留给你稍微想想吧:-)

后来，实现了霍夫曼解法，对于比较复杂的案例，两种解法得到结果对比，终于可以明确解法一的不足地方了！

“反过来想每次合并是两段长度之和。于是就变成了Huffman问题了。”
“解释一下样例一，10分割为4和6，代价为10，6分割为3和3，代价为6，3分割为1和2，代价为3。总代价为10+6+3，即Huffman树中非叶节点的权值和。”

> 解法二：

1. 借助上述的霍夫曼算法，集合A {a1,a2,…,an}作为权值，构造霍夫曼树，即最优权值二叉树。

2. 累加所有非叶子节点的权值，即所求的结果最小代价。

# 链接

Github上的示例代码