贪心算法理解
- 针对一组数据，定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。这类问题首先要联想到贪心算法。
- 每次选择当前情况下，在对限制值同等共享量的情况下，对期望值贡献最大的数据。这种问题可以用贪心算法解决。
- 举例验证贪心算法产生的结果是否是最优的。
用贪心算法解决问题的思路，并不总能给出最优解。
在一个有权图中，从顶点S开始，找一条到顶点T的最短路径（路径中边的权值和最小）。
贪心算法的解决思路是，每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点T。前面的选择，会影响到后面的选择。即便第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。
贪心算法实战
分糖果
m个糖果分给n个孩子，m<n。每个糖果的大小不等，每个孩子对糖果大小的需求也不一样，糖果大小需要>=孩子对糖果大小的需求，最多能满足多少个孩子。从需求小的孩子开始分配糖果，然后每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样的分配方案是能满足的孩子个数最多的方案。
钱币找零
不同面值的钱币，不同的张数，支付K元，最少需要多少张纸币。先用面值最大的来支付，如果不够，就继续用更小一点面值的，以此类推。
区间覆盖
有n个区间，区间的起始端点和结束端点各不相同。从这n个区间中选出一部分区间，这部分区间满足两两不相交。最多能选出多少个区间。（任务调度、教师排课）每次选择的时候，左端点跟前面的已经覆盖的区间不重合的，右端点尽量小的，可以让剩下的未覆盖区间尽可能的打，就可以放置更多的区间。
实现霍夫曼编码
一个包含1000个字符的文件，每个字符占1个byte(1byte=8bits)，存储这个文件需要8000bits。
1000个字符中质保函6中不同的字符，分别是a、b、c、d、e、f。三个二进制位（bit）就可以表示8个不同的字符，为了尽量减少存储空间，每个字符用3个二进制位来表示，存储这个文件只需要3000bits。
a(000)、b(001)、c(010)、d(011)、e(100)、f(101)
霍夫曼编码思想：
- 霍夫曼编码不仅考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同选择不同长度的编码。霍夫曼编码用这种不等长的编码方法，来进一步增加压缩的效率。
- 根据贪心的思想，可以把出现频率比较多的字符，用稍微短一些的编码；出现评率比较少的字符，用稍微长一些的编码。
- 为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。在解压缩的时候，每次读取尽可能长的可解压的二进制串。
霍夫曼编码实现：：
把每个字符看做一个节点，并且辅带着把频率放到优先级队列中。从队列中取出频率最小的两个节点A、B，然后新建一个节点C，把频率设置为两个节点的频率之和，并把新节点C作为A、B的父节点，再把C节点翻入到优先级队列中，重复这个过程，直到队列中没有数据。
（构造的优先级队列根据频率的不同，各不相同，极端退化成近似链表的结构，除了最后一层都走一个叉，1、01、001、0001、00001、00000）给每一条边加上一个权值，指向左子节点的边标记为0，指向右子节点的边，标记为1，从根节点到叶子节点就是叶子节点对应字符的霍夫曼编码。
（最理想情况，完全二叉树00、01、10、11）