首页 > 试题广场 >

关于堆数据结构，下面描述中正确的有（）

[不定项选择题]
关于堆数据结构，下面描述中正确的有（） 
  • 可以用堆实现优先队列（priority_queue）
  • 使用堆可以实现排序算法，复杂度为N * log N
  • 从M个元素中查找最小的N个元素时，使用大顶堆的效率比使用小顶堆更高
  • 在大顶堆中，第N层中的所有元素比第N+1层中的所有元素都要大
  • 堆数据结构可以用数组方式存储，存储的是一棵完全二叉树
查看正确选项
添加回答
凉风起天末头像 凉风起天末
关于C选项：利用堆结构解决top K（这里是min K）问题有两种实现方式，以本题的min K为例：

小顶堆思路：构建一个容量为n的堆，建堆时间为n，此后每次都弹出堆顶元素（最小元素）再调整，一共弹 K 次，每次调整时间为log(n)，所以时间复杂度是 n+K*log(n)；

大顶堆思路：只维护一个容量为 K 的堆，所以建堆的复杂度为 K，此后遍历数组剩下的所有元素（n-K个），每个元素都要和堆顶的元素进行比较，如果比堆顶大，则忽略，说明该元素不是最小K个值，复杂度是1，如果比堆顶小，则将该元素插入堆中并调整堆结构（称之为堆更新，堆更新发生的概率可参见博客，博客是以Top K为例进行分析的，Min K结论相同：牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网 (nowcoder.com)），这里直接给出堆更新操作发生的次数期望E，约为ln(n-k+1)+0.5772，那么不更新的期望便为(n-K)-E，每次更新（堆调整）的复杂度为 log(K)，所以最坏时间代价为：K + (n-K) * log(K)；
结合概率得到平均时间复杂度约为：K + E * log(K) + [(n-K)-E] * 1 ≈ ln(n-k+1)*log(K)+n；

下面我们来分析一下二者的代价，假设数据总量固定为10w，要求min K问题，将K作为变量，画出二者的函数图像（如下），可见，对于不同的 K 值，方法二（局部堆）普遍比方法一好（但是一定要注意把概率考虑进去，否则得出的结果是局部堆的最坏情况）。


而如果将 K 值固定为5000，将数据总量 n 作为变量又如何呢？？同样的，画图观察（如下），可见，还是方法二好一点。


局部堆（K堆）方法的特点是，堆顶在比较过程中起到了关键作用，大部分情况下，数据都被堆顶元素给拒之门外，只有少部分数据能进入堆中更新数据，另外空间效率也比较优秀。
全局堆（N堆）方法的特点是，当K非常小时，也能取得优秀的效率，但是当K增大时，代价就变大了，同时需要一个充分的空间来容纳所有数据。
结论：在以下两种情况下，局部堆比全局堆好用：
1、K相对较大，此时即使是最坏情况，局部堆也优于全局堆；
2、数据集没有明显规律，或者不是总体降序（min K），概率能够发挥作用；
编辑于 2023-10-09 16:20:10 回复(9)
Yeloran头像 Yeloran
发表于 2022-03-23 17:02:38 回复(2)
M阳头像 M阳
C选项我理解的是说从大顶堆不断从叶子节点中寻找最小的，然后删掉，再在叶子节点中寻找最小的，这样直至找到N个最小的为止，在N不是1时，不需要修改堆，反复查找叶子节点中最小的就可以了，不知道这样理解对不对
发表于 2019-09-17 09:57:01 回复(5)
Hesetone头像 Hesetone
C选项不太认同，M和N关系不知道吧，万一我在1w个元素中查询最小的1个值呢，也是大顶堆效率更高吗？貌似不是吧。等大佬来解释下。
发表于 2019-03-25 20:56:22 回复(5)
无可忧头像 无可忧
C不一定吧，
发表于 2022-08-11 10:33:49 回复(0)
是郑不是鄭头像 是郑不是鄭
c选项里： 1，小顶堆每次弹出堆顶，调整堆需要N次。 2，大顶堆每次弹出堆顶，调整堆，重复M-N次，留下的就是最小的N个元素
发表于 2022-07-14 15:48:26 回复(1)
已注销头像 已注销
收藏+1
发表于 2022-03-16 21:13:49 回复(0)
吃不饱的海洋头像 吃不饱的海洋
维护一个容量为M的堆 当个数小于M时 大根堆小根堆时间复杂度相等 当个数大于M时 小根堆:面对大于根和小于根的新数字你都需要调整堆 因为你不能确定这个数字是否比堆内其他元素的大小关系。 大根堆:如果新数字小于根 则调整堆 反之可以不做调整。
发表于 2022-02-22 11:44:59 回复(0)
Juventus-小九头像 Juventus-小九
堆数据结构是用数组方式存储，存储的是一颗完全二叉树
发表于 2022-02-18 16:03:32 回复(0)
aaa---头像 aaa---
<p>插眼</p><p><br></p><p><br></p>
发表于 2020-10-21 23:33:52 回复(0)
天尊墨宇头像 天尊墨宇
选ABCE
发表于 2020-07-19 07:26:37 回复(0)
拼命也要幸福头像 拼命也要幸福
堆排序的思想就可以很好的解决这个问题。创建小顶堆，然后每次将堆顶最小元素抛出，循环M次即可获取最小的M个数   c应该错了
发表于 2019-09-07 13:48:29 回复(0)
提交观点

问题信息

C++工程师 小米集团 测试工程师 2019 堆 Java工程师
来自：小米2019秋招软件开...
上传者：小小
难度：
12条回答 5118浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号