第八章第一节 贪婪算法
贪婪算法分阶段工作，每个阶段作出最优选择，而最后的结果也是最优的；如Dijkstra算法、Prime算法、Kruskal算法；而用贪婪算法处理网络流问题则得不到最优解。下面介绍几个使用贪婪算法的解决方案。
简单的调度问题
有作业P_1, . . . , P_N，它们对应的运行时间分别为t_1, . . . , t_N，而处理器只有一个；要将这些作业的平均完成时间最小化(作业一旦开始处理，就必须运行直到完成)，那么，这些作业平均完成时间最小的解决方案是按运行时间由小到大进行处理，这就是一种贪婪算法。对于多个处理器就是按运行时间由小到大轮流进行分配。
赫夫曼编码
将一段字符进行编码，以使得这段字符被编码后长度最短；显然，ASCII编码可以满足每个字符被编码后可被区分从而可正确解码，但是其长度过长；给定一段字符，对其中的每个字符进行赫夫曼编码，即如下的赫夫曼算法。
先介绍编码树，将编码的字符以树组织，编码第k位为0则进入第k层(由上至下)的左分支，第k位为1则进入第k层(由上至下)的右分支；
对一段字符，由C种字符组成，初始时每个字符都是一个单节点树，每次选择频率和最小的两个树，生成一个以这两个树为子树的新树；直到只有一个树。根据这些字符对应节点的位置即可得到其编码，这就是赫夫曼编码。