贪心算法（哈夫曼编码以及最小生成树：Kruskal算法和Prim算法）_用 kruskal 贪心算法构造霍夫曼编码java

作者：weixin_40725706 | 2024-06-09 10:14:01

踩

用 kruskal 贪心算法构造霍夫曼编码java

贪心问题

具有的性质如下：
贪心选择性：每一步贪心选出来的一定是原问题的最优解的一部分
最优子结构：每一步贪心选完后会留下子问题，子问题的最优解和贪心选出来的解可以凑成原问题的最优解

贪心选择性：每次贪心选频率最低的两个，那频率最低的两个的编码一定是原问题的最优解的一部分；
最优子结构：每次贪心选走的两个后，剩下的最优编码和贪心选走的那两个的最优编码一起可以合成原问题的最优编码。

定义：

没有任何码字是其他码字的前缀

作用：
简化解码过程：没有任何一个字符的编码是另一个字符编码的前缀。这样的编码具有唯一可解析性，即通过编码可以唯一地解码出原始的字符序列。这是因为在解码时，我们可以一直读取编码，直到找到与某个字符匹配的编码为止，而不会有歧义。

解码过程需要前缀码的一种方便的表示形式：
二叉树

最优编码方案：

总是对应一颗满二叉树

给定一棵对应前缀码的树T，对于字母表

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/693650