电话:0731-83595998
导航

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

来源: 2017-10-20 14:14

 (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

编辑推荐:

下载Word文档

温馨提示:因考试政策、内容不断变化与调整,长理培训网站提供的以上信息仅供参考,如有异议,请考生以权威部门公布的内容为准! (责任编辑:长理培训)

网络课程 新人注册送三重礼

已有 22658 名学员学习以下课程通过考试

网友评论(共0条评论)

请自觉遵守互联网相关政策法规,评论内容只代表网友观点!

最新评论

点击加载更多评论>>

精品课程

更多
10781人学习

免费试听更多

相关推荐
图书更多+
  • 电网书籍
  • 财会书籍
  • 其它工学书籍
拼团课程更多+
  • 电气拼团课程
  • 财会拼团课程
  • 其它工学拼团
热门排行

长理培训客户端 资讯,试题,视频一手掌握

去 App Store 免费下载 iOS 客户端