堆和堆排序在笔试题面试题中的应用

[结构化面试题型]结构化面试题型结构化面试只要考生在考前有一个充分的准备，面试成绩是可以迅速提高的。但要想在面试中取得好成绩，就必须对结构化面试的各种题型及其解题思路有一个清晰的把...+阅读

堆和堆排序在笔试题面试题中的应用；

使用堆解决可以解决下列几个问题，它们在笔试面试题中可以称为经典和烫手的：

1. 构建哈夫曼代码怎样提升性能?

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

之前我们遇到哈夫曼编码，往往关注的是其思想，然而每次取出最小的2个元素的过程，却涉及到排序、求极值的问题。这时候用堆来维护这个队列，每次还能将取出的两个最小值的和插到堆里，非常方便，减少了运行时间。

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

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

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

这个就是TOP(K)问题了，可以建立100万个元素的最小二叉堆，后面的数和根部进行比较，如果大于根部，进行堆调整

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

该问题我整理成了另一篇文章。里面附有源码测试;

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

意思就是，维护一个堆，该堆存放了所有小文件的最小值。每次取出最小值min(属于小文件A)，将小文件A的下一个最小值再插入到A。持续下去，问题解决。

其他的相关笔试经验：

农村商业银行笔试分享女大学生应聘银行心得经验客服笔试题让你思维灵活