贪心生成最优编码的思路分析
贪心生成最优编码的思路分析 #
目标：求字符编码
首先得先想到用二叉树表示编码，节点即为字符，边为编码。
然后优化目标（目标函数）即为： f(x) = w(x)*l(x)
- w(x) 为 字符x的频率
- l(x) 为 字符编码的长度
决策目标：巧妙安排二叉树的结构，使得目标函数值最小。
最优编码树性质一：对于最优编码树，频率最小的两个节点深度最大，且为兄弟。
证明：
-
深度最大显然，否则深度最大的频率更大，会使得目标函数值增大。
-
若最小的节点有兄弟，且其兄弟不是次小的，则可以让次小的节点与该节点交换，使得目标函数更小。
-
若最小的节点没有兄弟，则可以将该节点与其父亲交换，去掉“父亲”，可以使得目标函数更小。
有了这个性质，我们便可以先将两个频率最小的点连起来作兄弟。但为了进一步构造最优编码树，还需要第二个原则。
最优编码树性质二： 对于最优编码树，删掉频率最小的节点（两个叶子节点），则其父亲变成了叶子结点，另其频率为两孩子频率之和，则新的编码树仍然是最优编码树。
证明：f1为删之前，f2为删之后目标函数值，最小两个节点为x1,x2, 则有
f1 = f2 + x1 + x2。
已知f1最小，则f2也是最小的，否则调整新的编码树使其变为最优编码树，则f1更小，与已知f1最小矛盾。故新编码树也为最优编码树。
有了这第二个性质，我们已知新的编码树为最优编码树，则根据性质一， 新编码树频率最小的节点为兄弟。递归这个过程，直到所有节点都纳入编码树（叶子节点）。
例: 将两个频率最小的点连起来作兄弟，然后用这两个点的父亲代替这两个点，求剩余点的最优编码树。