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

时间:2018-12-31 12:00:00 资料大全 我要投稿

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

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

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

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

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

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

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

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

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

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

资料共享平台

堆和堆排序在笔试题面试题中的应用》(http://meiwen.anslib.com)。

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

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

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

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

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

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

其他的相关笔试经验

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

【堆和堆排序在笔试题面试题中的应用】相关文章:

1.笔试题(堆和栈)

2.外企面试试题中的选编

3.面试技巧:在另类问题中胜出

4.笔试题中的财会部分试题

5.笔试题中的常识题1

6.职业测评技术在面试中的应用

7.英语面试须知的试题和答案

8.电信面试和笔试题搜集