数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?

王争 2018-12-17
基础的数据结构和算法我们基本上学完了,接下来几节,我会讲几种更加基本的算法。它们分别是贪心算法、分治算法、回溯算法、动态规划。更加确切地说,它们应该是算法思想,并不是具体的算法,常用来指导我们设计具体的算法和编码等。
贪心、分治、回溯、动态规划这 4 个算法思想,原理解释起来都很简单,但是要真正掌握且灵活应用,并不是件容易的事情。所以,接下来的这 4 个算法思想的讲解,我依旧不会长篇大论地去讲理论,而是结合具体的问题,让你自己感受这些算法是怎么工作的,是如何解决问题的,带你在问题中体会这些算法的本质。我觉得,这比单纯记忆原理和定义要更有价值。
今天,我们先来学习一下贪心算法(greedy algorithm)。贪心算法有很多经典的应用,比如霍夫曼编码(Huffman Coding)、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。最小生成树算法和最短路径算法我们后面会讲到,所以我们今天讲下霍夫曼编码,看看它是如何利用贪心算法来实现对数据压缩编码,有效节省数据存储空间的

如何理解“贪心算法”?

关于贪心算法,我们先看一个例子。
假设我们有一个可以容纳 100kg 物品的背包,可以装各种物品。我们有以下 5 种豆子,每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大,我们如何选择在背包中装哪些豆子?每种豆子又该装多少呢?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(122)

  • cirno
    1、由最高位开始,比较低一位数字,如高位大,移除,若高位小,则向右移一位继续比较两个数字,直到高位大于低位则移除,循环k次,如:
    4556847594546移除5位-》455647594546-》45547594546-》4547594546-》4447594546-》444594546

    2、由等待时间最短的开始服务
    2018-12-17
    9
    139
  • 开心小毛
    找零问题不能用贪婪算法,即使有面值为一元的币值也不行:考虑币值为100,99和1的币种,每种各一百张,找396元。
     动态规划可求出四张99元,但贪心算法解出需三张一百和96张一元。

    作者回复: 是的 👍

    2018-12-31
    3
    71
  • Alexis何春光
    留言里feifei说的两种解决思路都是错的,给的链接也失效了.... 老师可以回复一下防止误导后来的同学呀!
    以及没有看出来霍夫曼算法和贪心算法有什么联系,求详细讲解
    2019-01-12
    5
    27
  • Jalyn
    想知道目前没掉队的有多少 哈哈

    作者回复: 慢慢学 不着急😄

    2018-12-17
    1
    26
  • qinggeouye
    1、在一个非负整数 a 中,希望从中移除 k 个数字,让剩下的数字值最小,如何选择移除哪 k 个数字呢?

    整数 a,由若干位数字组成,移除 k 个数字后的值最小。从高位开始移除:移除高位数字比它低位数字大的那个;K 次循环。

    也可以用 Top K 排序,求出 K 个最大的数字,移除。

    2、假设有 n 个人等待被服务,但是窗口只有一个,每个需要被服务的时间长度是不同的,如何安排被服务的先后顺序,才能让这 n 个人总的等待时间最短?

    每个人需要被服务的时间不一样,但所有人加起来总的被服务时间是固定的。

    题意是求 n 个人总的等待时间,每个人在被服务之前,所经过的等待时间是不同的。

    而当前被服务的人所需的服务时间,会累加到剩下的那些等待被服务人的等待时间上。

    要使 n 个人总的等待时间最短,那么每次安排服务时间最短的那个人被服务:堆排序(小顶堆)。


    另外,@Alexis何春光 的留言,第一句话表示赞同。
    2019-01-19
    24
  • feifei
    1,在一个非负整数 a 中,我们希望从中移除 k 个数字,让剩下的数字值最小,如何选择移除哪 k 个数字呢?
    对于此题,我的求解思路是每次选择数据的最高位的数据值进行移除,这样我们每次选择的移除的数值都是最大的,剩下的数值也是最小的。
    比如,数据5892,将数据拆成5000,800,90,2,然后使用大顶堆来进行存储,然后每次移除大顶堆中堆顶最大的元素。

    2,假设有 n 个人等待被服务,但是服务窗口只有一个,每个人需要被服务的时间长度是不同的,如何安排被服务的先后顺序,才能让这 n 个人总的等待时间最短?
    对于此问题,我的求解思路是让待时间最长的来安排先后顺序
    比如,现在有3个人,a、b、c,a等待了10分钟,b待待了20分钟,c待待了30分钟
    同样使用大顶堆来进行存储等待时间,堆顶的元素就是当前等待时间最长的人
    然后每次从堆拿出堆顶元素的人来进行服务,这样就可以让这n个人的总的等待时间最短。




    对于学习的贪心算法,老师虽然只进行了理论讲解,但我看完了老师所讲的,我对贪心算法的理解有了一定的认识,我就试着把贪心算法的内容中涉及的东西,都翻译成了代码,
    感觉收获良多,也把这个分享给童鞋,希望对他们有帮助。
    1,这是第一个示例,背包中豆子的最大价值的问题
    https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/case1
    2,这是孩子分糖果的问题
    https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/case2
    3,这是钱币支付的问题
    https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/case3
    4,这是区间覆盖的问题
    https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/case4
    5,这是霍夫漫编码的实现
    https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/algorithm/greedyAlgorithm/huffman

    欢迎大家与我交流,也欢迎老师给我指正,谢谢
    2018-12-20
    9
    18
  • 🐱您的好友William🐱
    给大家提个醒,货币找零问题如果没有C1货币的话得用动态规划去解,如果出现{C2,C7,C10}货币找零11块的时候使用greedy就会出现找不开的情况。。。。有C1就不会出现找不开的情况且多个C1可以构成任何面值,所以这种情况下使用greedy是对的!(leetcode322题调了一下午的路过。。。)
    2018-12-17
    11
  • luxinfeng
    老师能详细讲讲区间覆盖这个问题的选择过程么?
    2018-12-17
    11
  • 睡痴儿😑
    第一个题,可以反着来想。给定另一个数组,怎么从中原本的中挑出n-k个,使其值最小。
    首先第一位必须要是最小的一个,但是因为有顺序,所以只能是从0到n-1-k个中挑一个最小的,下标为m。以后依次类推,从m到n-k中挑一个最小的。如果有相等的情况,以下标小的为准。
    第二个,就是从小到大排序即可。
    2019-01-22
    8
  • www.xnsms.com小鸟接码
    霍夫曼编码,用一个树来避免某个字符的编码是另一个字符编码的前缀,真的是好巧妙
    2019-01-06
    8
  • 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-22
    6
  • Jerry银银
    打个卡,我还在
    2018-12-19
    6
  • 小美
    老师 区间覆盖的问题, (1-5) 和 (2-4) 中为什么选(2-4) 方便老师解释下吗, 贪心不能全局最优 用贪心 如何在这个问题上全局最优呢

    作者回复: 24让剩下的没有被覆盖的区间最大 如果你选15 那我完全可以用24替代15 这样子 只有更好 不会更差

    2018-12-17
    6
  • CathyLin
    课后思考:
    1. 第一道题一开始没有想到...以为直接删除最大的那 k 个数字就好了,后来举了几个样例发现是错的。然后看了评论区小伙伴们的留言,太奇妙了!!!我是真的没有想到这种思路😫
    1) 从高位往低位走,删掉高位比低位大的数;为什么这样子是好的呢?试想:
    4596743 如果我们只能删一位,我们会删第三位的 9,因为这样就相当于是把高位给减少了,变成了456743,但是如果删 6,变成了 459743 则没有之前那个优。删后面的数更起不到高位的那种作用。
    2) 如果所有数字都是递增的,那么我们删除倒数
    k 个数字就好了。

    2. 想让所有人的等待时间最短,那么我们得先处理服务时间短的,尽快把他们处理完了才能够处理后面的人!

    贪心反思:有些时候思路还是难以打开,可能还是跟老师说的那样,多练习、多积累才是最好的学习方法!
    2019-07-31
    4
  • coder
    区间覆盖问题,把区间按照结束时刻排序,每次选择最早结束且没有冲突的区间即可
    2019-04-15
    4
  • Ying
    经过这种编码压缩之后,这 1000 个字符只需要 2100bits 就可以了------- ,这个位置 我算了一下各个和相加,结果是1910bits吧, 是我算的不对吗 ?
    2019-01-11
    3
  • 白若
    思考题(自己的想法,不知道对不对,希望老师能给我评论。)

    1.从前往后两两比较,若前数大于等于后数,选择移除。如果一轮下来没达到k个数,就移除最后的m个数,m为k-已选出个数。
    2.时间越短位置越靠前。
    2018-12-17
    3
  • 蒋礼锐
    第一个问题不知道0可不可以被保留在最高位,如果可以的话那么应该每次移除该整数的非零最高位,比如909090,k为2的话,最小的值应该是0090,如果0不能在最高位,就贪心算法就不能得到最优解了,跟之前的加权图一样,因为决策会相互影响。

    第二个问题假设5个人,时间分别是1-5-3-4-2分钟,等待的时间是每个人等待时间的总和即单个服务时间*剩余等待人数。不管现在服务的是谁,剩余等待的人数是不会变的,所以只需要找单个服务时间最小的,即按服务时间数升序服务即1-2-3-4-5,总的时间为1*4+2*3+3*2+4*1=20

    就像春运取票,你如果是去取售票机上买票的话,后面排队着急的人会说,让我先取吧,我直接取很快。这样集体时间效率最高,但是对单个个体来说就不一定了,比如之前那个要买票的。
    2018-12-17
    1
    3
  • 天,很蓝 ~
    如果文档中只有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-20
    3
    2
  • 乐凡
    老师,我觉得那个霍夫曼编码可能有点缺陷,就是不同字符在字符串中出现的频率很接近,那如果还是按照给每个字符用不同长度的二进制码表示,很有可能会比前面用相同二进制码表示耗费的空间多(亲自测过)。我觉得每一个字符在字符串中出现的频率需要满足一定的大小差距,这样使用空间才会比使用相同数量的二进制码更少。这个大小差距点的公式不太好算,笨一点的办法就是用两种方式比较下占用空间大小。

    作者回复: 给个你的测试用例我看看

    2019-03-21
    2
收起评论
99+
返回
顶部