哈夫曼树

假设一堆字母有一串01编码，那其就对应一棵二叉树，每个字母是叶子节点，每一个字母的编码都不会出现在其他字母的前缀里面
一个哈夫曼树就是一个二叉树带权路径长度之和最小。求完数，给每个边赋值01之类左右子树不同

满足的性质
1：所有点的度数肯定不是1
2: 一定存在一个最优解使得权值最小的两个点一定可以作为兄弟节点
证明：1：首先需要证明最优解一定在最下层，反证法不在最下层如果交换到最下层，结果不会变差
2： 如果两者不是兄弟，那么可以邻项交换，变成兄弟节点
最优子结构：
这个比较好办。现在是n个点，弄完第一步后剩n-1个点，要证明这n-1个点也得构成最优树才能保证n个点也是最优树。证明：
设n-1个点构成了T‘树，总长度为len’。此时n个点的树的
len=len‘+cntx+cnty
显然len’最优才能保证len最优。
所以满足最优子结构和第一步正确性，算法是合理的。

二路归并算法最坏时间复杂度是剩了一个节点n+m-1