37 | 贪心算法：如何用贪心算法实现Huffman压缩编码？
王争
该思维导图由 AI 生成，仅供参考
基础的数据结构和算法我们基本上学完了，接下来几节，我会讲几种更加基本的算法。它们分别是贪心算法、分治算法、回溯算法、动态规划。更加确切地说，它们应该是算法思想，并不是具体的算法，常用来指导我们设计具体的算法和编码等。
贪心、分治、回溯、动态规划这 4 个算法思想，原理解释起来都很简单，但是要真正掌握且灵活应用，并不是件容易的事情。所以，接下来的这 4 个算法思想的讲解，我依旧不会长篇大论地去讲理论，而是结合具体的问题，让你自己感受这些算法是怎么工作的，是如何解决问题的，带你在问题中体会这些算法的本质。我觉得，这比单纯记忆原理和定义要更有价值。
今天，我们先来学习一下贪心算法（greedy algorithm）。贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。最小生成树算法和最短路径算法我们后面会讲到，所以我们今天讲下霍夫曼编码，看看它是如何利用贪心算法来实现对数据压缩编码，有效节省数据存储空间的。
如何理解“贪心算法”？
关于贪心算法，我们先看一个例子。
假设我们有一个可以容纳 100kg 物品的背包，可以装各种物品。我们有以下 5 种豆子，每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了贪心算法的应用，以Huffman压缩编码为例进行了详细阐述。贪心算法的核心思想是在满足限制值的情况下，选择对期望值贡献最大的数据，以期望值最大为目标。文章通过具体例子，如分糖果和钱币找零问题，深入解释了贪心算法的应用和实战分析。同时，文章也指出了贪心算法并不总能给出最优解的情况，需要谨慎应用。此外，文章还介绍了霍夫曼编码的原理和应用，以及如何根据字符出现频率的不同，给不同的字符进行不同长度的编码。最后，文章提出了两个课后思考问题，引发读者思考和讨论。总的来说，本文深入浅出地介绍了贪心算法及其在实际问题中的应用，对于想要了解贪心算法及其应用的读者具有很高的参考价值。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(234)
- 最新
- 精选
- 开心小毛找零问题不能用贪婪算法，即使有面值为一元的币值也不行：考虑币值为100，99和1的币种，每种各一百张，找396元。 动态规划可求出四张99元，但贪心算法解出需三张一百和96张一元。
作者回复: 是的 👍
2018-12-3113226 
Jalyn想知道目前没掉队的有多少 哈哈作者回复: 慢慢学 不着急😄
2018-12-171073
bingo@吴：wiki上的哈夫曼树是标准的生成步骤，老师这里举的例子是一种特殊情况，哈夫曼树构建的一般性方法在本科的教程上就写的很通俗了。 我用wiki里的值举个例子吧：原始集合的值是[2,3,4,4,5,7] 第一步：从原始集合中取出最小的两个值并将这两个值从原始集合中剔除，这两个最小的值相加得到一个新的值并加入原始集合，这两个小值作为这个新值的树叶，新值当然就是树根了。这一步执行之后原始集合就变成了这样： [ ⑤, 4,4,5,7] / \ 2 3 第二步：从更新后的集合中再取最小的两个值并剔除，同样相加得到新值加入到集合。这一步执行之后集合就变成了 [⑤, ⑧ ,5,7] / \ /\ 2 3 4 4 第三步，重复以上步骤，你懂得。结果是： [ ⑩, ⑧, 7] / \ / \ 5 ⑤ 4 4 / \ 2 3 第四步，结果是： [ ⑩, 15,] / \ / \ 5 ⑤ 7 ⑧ /\ / \ 2 3 4 4 最后一步，结果是： (25) (打不出圆圈了，用这个代替，应该不难理解，嗯) / \ ⑩ 15 / \ / \ 5 ⑤ 7 ⑧ /\ / \ 2 3 4 4 wiki哈夫曼树链接：https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81 ps:大半夜手打，排版扎心作者回复: 👍啊 就喜欢你这么极致的人！
2019-02-22562
蚂蚁内推+v老师 区间覆盖的问题， (1-5) 和 (2-4) 中为什么选(2-4) 方便老师解释下吗， 贪心不能全局最优 用贪心 如何在这个问题上全局最优呢作者回复: 24让剩下的没有被覆盖的区间最大 如果你选15 那我完全可以用24替代15 这样子 只有更好 不会更差
2018-12-17714
发飙的蜗牛个人觉得分糖果不能使用贪心算法，如果使用可以加个条件一个孩子只能分一个糖果，因为可能存在孩子的满意度大于最小的糖果，但是最小的两个的和刚好满足。这个情况贪心就无法满足了。作者回复: 哈哈，你很细心，是的，一个孩子最多一个糖果
2019-02-289
天，很蓝 ～如果文档中只有4个字符，分别是a，b，c，d出现的频率相等，都是100次。如果用00，01，10，11分别表示a，b，c，d的话，总共需要800bit就可以了。但是如果用霍夫曼编码的话，用1，01，001，000分别表示a，b，c，d的话反而需要900bit。这个是不是说明霍夫曼编码有时候是起不到压缩作用的？望老师解答作者回复: 用霍夫曼编码也是00、01、10、11的，你再看下霍夫曼编码的原理吧
2019-06-2052
乐凡老师，我觉得那个霍夫曼编码可能有点缺陷，就是不同字符在字符串中出现的频率很接近，那如果还是按照给每个字符用不同长度的二进制码表示，很有可能会比前面用相同二进制码表示耗费的空间多（亲自测过）。我觉得每一个字符在字符串中出现的频率需要满足一定的大小差距，这样使用空间才会比使用相同数量的二进制码更少。这个大小差距点的公式不太好算，笨一点的办法就是用两种方式比较下占用空间大小。作者回复: 给个你的测试用例我看看
2019-03-2132
William霍夫曼编码原理 , 不是要求左子树小于右子树么, 按照您的写法, 都依次排列在了右子树啊.作者回复: 没这个要求啊
2019-08-012
likun老师 你给的钱币找零的例子是可以用贪心回去到最优解 但存在其他面额的例子对于贪心是获取不到最优解的 为什么你给的例子用贪心就能获取到最优解呢？作者回复: 😁，你观察的很仔细，因为给出的钱币面值有特点，所以可以用贪心来解决。你可以网上搜下，钱币找零问题，有一大堆不同的场景和解法。
2019-06-20
djfhchdh上面霍夫曼编码构造出的那个树形结构，是不是解码也可以用？？作者回复: 是的
2019-05-23
收起评论
