首页 > 试题广场 >

以下序列不是堆的是()

[单选题]
以下序列不是堆的是() 
  • (100,85,98,77,80,60,82,40,20,10,66)
  • (100,98,85,82,80,77,66,60,40,20,10)
  • (10,20,40,60,66,77,80,82,85,98,100)
  • (100,85,40,77,80,60,66,98,82,10,20)
查看答案及解析
添加回答
zhisheng_blog头像 zhisheng_blog

已知一个序列，比如{100,6070,50,32,65}，怎么判断是不是堆？

答案：把这个序列看成数组型的二叉树，如果根结点是i，左子树是2*i，右子树是2*i+1。

堆分为最大堆与最小堆。

  1. 最大堆中所有父节点都比左子树、右子树大，比如已知序列，画成堆就是： 
    这里写图片描述 
    所以已知序列是个最大堆。

  2. 最小堆中所有父节点都比左子树、右子树小，比如{32,50,60,70,100,65},画成堆： 
    这里写图片描述

符合以上两种情况的序列就是堆

发表于 2016-08-17 09:14:41 回复(1)
鬼风神梦头像 鬼风神梦
堆要么是最大堆，要么是最小堆，比较i节点与2*i节点及2*i+1的大小关系，看是否一致。如果每对都一致则是，否则不是。
发表于 2016-09-08 22:14:00 回复(0)
牛客910008号头像 牛客910008号
最大（小）堆，所有节点都大（小）于其孩子节点，i  位置节点的孩子节点为 2i 和 2i+1 ，i 节点的父节点为 i/2
注意 i 是从1开始的。
编辑于 2016-07-27 20:17:29 回复(0)
like头像 like
D
发表于 2015-01-04 11:38:24 回复(0)
yoyohehe头像 yoyohehe
一楼说的对
发表于 2016-11-19 15:23:41 回复(1)
D.JJ头像 D.JJ
 堆的序列可以按二叉树排列，完成过程中父节点均不大于或均不小于子节点，以此来判断出
发表于 2016-08-02 17:15:23 回复(0)
Ace雅头像 Ace雅
将每个序列输出成二叉树的形状，序列从左到右，堆是从上到下，从左到右依次排序，每个结点都>=左右孩子为大顶堆,每个结点都<=左右孩子为小顶堆。D选项中100的右孩子为40，40的左右孩子60和66大于40，不满足要求
发表于 2015-09-18 23:00:09 回复(0)
提交观点

问题信息

堆
难度：
7条回答 13266浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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