首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
基础的数据结构和算法前面基本学完了，接下来几节，将会涉及到几种更加具体的算法。它们分别是贪心算法、分治算法、回溯算法、动态规划。准备来说，它们是算法思想，并不是具体的算法，常用来指导我们设计具体的算法和编码等。
这几个算法思想原理虽然简单，但是我们要结合具体的问题，感受这些算法是怎么工作的，是如何解决问题的，要在问题中体会这些算法的本质。
本节先来学习一下贪心算法（greedy algorithm）。贪心算法有很多经典的应用，如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。
今天我们主要学习下霍夫曼编码，看看它是如何利用贪心算法来实现对数据压缩编码，有效节省数据存储空间的。
如何理解“贪心算法”？
假设有一个可以容纳 100kg 物品的背包，有如下5种总量和总价值都各不相同的豆子。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？
实际上，只要先算一算每个物品的单价，按照单价由高到低依次来装就好了。单价从高到低排列，依次为黑豆、绿豆、红豆、青豆、黄豆，所以，我们可以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆。
这个解题思路的本质就是贪心算法。贪心算法解决问题的步骤如下：
第一步，当看到这类问题：针对一组数据，定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。首先要联想到贪心算法。
第二步，尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
第三步，举几个例子看贪心算法产生的结果是否是最优的。大部分情况下，举几个例子验证一下就可以了。严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。而且，从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。
实际上，用贪心算法解决问题的思路，并不总能给出最优解。
例如，在一个有权图中，从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。贪心算法的解决思路是：每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点 T。求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9。
但是，这种贪心的选择方式，最终求的路径并不是最短路径。路径 S->B->D->T 才是最短路径，因为这条路径的长度是 2+2+2=6。
这个问题上，贪心算法不工作的主要原因是：前面的选择，会影响后面的选择。即便前面选择的是最优的走法，但是可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。
贪心算法实战分析
贪心算法的关键是多练习。
分糖果
假设有 m 个糖果和 n个 孩子，但是 m < n，所以糖果只能分配给一部分孩子。每个糖果的大小不等，分别是 s1，s2，s3，……，sm。每个孩子对糖果大小需要也不一样，分别是g1，g2，g3，……，gn。只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。那怎么分配糖果，能尽可能满足最多数量的孩子？
这个问题可以抽象成：从n个孩子中，抽取一部分孩子分配糖果，让满足的孩子的个数（期望值）是最大的。这个问题的限制值就是糖果个数 m。
那如何使用贪心算法解决这个问题呢？因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们期望值的贡献是一样的。而对糖果大小需求小的孩子更容易被满足。
所以，我们每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。
钱币找零
假设我们有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。若现在要用这些钱来支付 K 元，最少要用多少张纸币呢？
生活中，我们肯定先用面值最大的钱来支付；如果不够，就继续用更小一点面值的，以此类推，最后剩下的用 1 元来补齐。在贡献相同期望值（纸币数目）的情况下，我们希望多贡献点金额，这样就可以让纸币数更少，这就是一种贪心算法的解决思路。
区间覆盖
假设有 n 个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？
这个问题的解题思路在很多贪心算法问题中都有用到，比如任务调度、教师排课等问题。解题思路为：假设这 n 个区间中最左端点是 lmin，最右端点是 rmax。这个问题就相当于，我们选择几个不相交的区间，从左到右将[lmin, rmax]覆盖上。
我们按照起始端点从小到大的顺序对这 n 个区间排序。我们每次选择的时候，左端点跟前面的已经覆盖的区间不重合的，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间。这实际上就是一种贪心的选择方法。
解答开篇
如何用贪心算法实现霍夫曼编码？
假设有一个包含1000个字符的文件，每个字符占一个 byte（1byte=8bits），存储这1000个字符就一共需要 8000bits，有没有更加节省空间的存储方式？
若这1000个字符中只包含6中不同字符，假设它们分别是a、b、c、d、e、f。而3个二进制位（bit）就可以表示8个不同的字符。这样，存储这1000个字符只需要3000bits就可以了。不过要想更加节省空间，需要使用到霍夫曼编码。它是一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间。
霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。出现频率比较多的字符用稍微短一些的编码；出现频率比较少的使用稍微长的一些编码，来进一步增加压缩的效率。
不过，霍夫曼编码因为是不等长的，每次应该读取1位、2位还是3位进行解码呢？这就导致霍夫曼编码解压缩起来很复杂。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。
假设这6个字符出现的频率高低依次为a、b、c、d、e、f。如下编码方式，任何一个字符的编码都不是另一个的前缀，在解压缩的时候，我们每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。经过这种编码压缩之后，这 1000 个字符只需要 2100bits 就可以了。
那怎么根据字符出现频率的不同，给不同的字符进行不同长度的编码呢？
我们把每个字符看作一个节点，并且辅带着把频率放到优先级队列中。我们从队列中取出频率最小的两个节点 A、B，然后新建一个节点 C，把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点。最后再把 C 节点放入到优先级队列中。重复这个过程，直到队列中没有数据。
接着给每一条边加上一个权值，指向左子节点的边我们统统标记为 0，指向右子节点的边，我们统统标记为 1，那从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。
内容小结
贪心算法使用的场景比较有限。这种思想更多的是指导设计基础算法。比如最小生成树算法、单源最短路径算法，这些算法都用到了贪心算法。
贪心算法的最难的一块是如何将要解决的问题抽象成贪心算法模型，只要这一步搞定之后，贪心算法的编码一般都很简单。贪心算法解决问题的正确性虽然很多时候都看起来是显而易见的，但是要严谨地证明算法能够得到最优解，并不是件容易的事。所以，很多时候，我们只需要多举几个例子，看一下贪心算法的解决方案是否真的能得到最优解就可以了。
课后思考
在一个非负整数 a 中，我们希望从中移除 k 个数字，让剩下的数字值最小，如何选择移除哪 k 个数字呢？
答：由最高位开始，比较低一位数字，如高位大，移除，若高位小，则向右移一位继续比较两个数字，直到高位大于低位则移除，循环k次，如：
4556847594546移除5位 -> 455647594546 -> 45547594546 -> 4547594546 -> 4447594546 -> 444594546。假设有 n 个人等待被服务，但是服务窗口只有一个，每个人需要被服务的时间长度是不同的，如何安排被服务的先后顺序，才能让这 n 个人总的等待时间最短？
答：每个人需要被服务的时间不一样，但所有人加起来总的被服务时间是固定的。题意是求 n 个人总的等待时间，每个人在被服务之前，所经过的等待时间是不同的。而当前被服务的人所需的服务时间，会累加到剩下的那些等待被服务人的等待时间上。要使 n 个人总的等待时间最短，那么每次安排服务时间最短的那个人被服务：堆排序（小顶堆）。
