2011年软考程序员考试复习笔试知识点整理(14)3

 (3)其他应用

　　可使用堆解决下列问题：

　　1.构建哈夫曼代码：

　　我们知道在构建哈夫曼树时，每次要选择集合中两个最小的元素，然后将元素值相加，合并为一个新节点，此时两个最小的元素的取出可以用HeapExtractMin函数来实现，产出的新节点需要插入到堆中，我们有MinHeapInsert函数来实现。

　　2.计算大型浮点数集合的和：

　　我们知道大浮点数和小浮点数相加，很可能会造成精度误差。所以可以每次从优先级队列中取出最小的两个数相加，和1的实现差不多。

　　3.将多个小型有序文件合并到一个大型有序文件中：

　　假设有 n个小型有序文件，建立一个大小为n的最小堆，每个有序文件贡献一个(如果有的话)，每次取出最小值插入到大型文件中，并且去掉该最小元素，并将它在文件中的后续元素插入到堆中,能够在o(lgn)的时间内从n个文件中选择要插入到大型文件中的元素。

　　4.在具有10亿个数值的集合中找到100万个最大的数：

　　建立100万个元素的最小二叉堆，后面的数和根部进行比较，如果大于根部，进行堆调整。

　　1.n×m遍扫描

　　【算法基本描述】n×m遍扫描

　　【算法复杂度】O(nm)

　　【算法思想】每次都扫描一遍数组，取出最大元素，这样扫描m遍就能得到m个最大的数。

　　2.排序后取最大m个数

　　【算法基本描述】对n个数排序，对拍完序后的序列取m个最大的数

　　【算法复杂度】视排序的复杂度，一般为O(nlogn)或O(n^2)

　　3.最小堆

　　【算法基本描述】一遍扫描+最小堆

　　【算法复杂度】O(nlogm) 遍历O(n) 最小堆O(logm)

　　【算法伪代码】

　　建立一个最小堆(优先队列)，最小堆的大小控制在m之内;

　　for 每个数：

　　if 这个数比最小堆的堆顶元素大：

　　弹出最小堆的最小元素，

　　*把这个数插入到最小堆;

　　最小堆中的m个元素就是所要求的元素;

　　中最小堆的作用就是保持里面始终有m个最大元素，且m个元素中最小的元素在堆顶。

　　【其他】如果要求n个数中取最小的m个，只要大顶堆即可

　　总结：当n与m差不多大时，采用复杂度较低的排序是比较可取的，因为简单。当m