首页 > 试题广场 >

一组记录排序码为(5 11 7 2 3 17),则利用堆排序

[单选题]
一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为 
  • (11 5 7 2 3 17)
  • (11 5 7 2 13 3)
  • (17 11 7 2 3 5)
  • (17 11 7 5 3 2)
  • (17 7 11 3 5 2)
  • (17 7 11 3 2 5)
查看答案及解析
添加回答
推荐
wangchenphoebe头像 wangchenphoebe
如果堆的有序状态因为某个节点变得比它的父节点更大而打破，那么就需要通过交换它和它的父节点来修复堆。从最后一个非叶结点逐渐往上浮，直到有序。

编辑于 2016-09-30 21:37:04 回复(19)
huixieqingchun头像 huixieqingchun
使用堆排序，一般都使用最大堆。
初始堆就是第一次排序时建立的堆的形状，可以将题目中的给的序列按层次写成完全二叉树的形式，再移动元素形成堆。
最后将堆再按层次遍历的方式写成序列的形式，即可得到答案。
发表于 2016-05-08 14:34:16 回复(3)
爱吃青菜皮卷面的byr头像 爱吃青菜皮卷面的byr
构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：
20和16交换后导致16不满足堆的性质，因此需重新调整
这样就得到了初始堆。
即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。
发表于 2017-02-23 21:39:47 回复(3)
BrainerGao头像 BrainerGao
发表于 2016-06-03 10:20:14 回复(3)
带不走的只有你的未来头像 带不走的只有你的未来
借用一下上面大牛的图，画的很清晰，不过需要补偿一点的是，应该说明一下：在开始调整之前，需要先比较调整点左右子树的大小，然后沿着大的分支进行“筛选”。
编辑于 2018-03-16 16:25:07 回复(2)
八月南溯头像 八月南溯
为啥是325，不应该是235么？

发表于 2019-06-06 15:53:43 回复(0)
戴戴crystal头像 戴戴crystal
C
从最后一个非叶子节点开始向上调整，如果不是最大的，则和子树中最大节点交换。
发表于 2018-06-15 14:09:16 回复(0)
dapengdeda头像 dapengdeda
堆排序算法解析（主要了解什么叫初始堆）：http://jingyan.baidu.com/article/5225f26b057d5de6fa0908f3.html
发表于 2016-06-04 20:40:47 回复(2)
考证换名头像 考证换名
从最后一个非叶节点开始！！！！
发表于 2020-03-05 18:21:53 回复(0)
小菲柱头像 小菲柱
一直下沉到根节点
发表于 2022-04-13 20:02:34 回复(0)
Juventus-小九头像 Juventus-小九
从最后一个非节点开始调整。
发表于 2022-02-18 16:00:13 回复(0)
新的一年换个名字头像 新的一年换个名字
0
发表于 2019-03-01 22:17:14 回复(0)
秋招快结束了又重启了？头像 秋招快结束了又重启了？
这题是让从大到小排序还是从小到大排序啊？
发表于 2018-11-06 18:57:46 回复(0)
그해여름头像 그해여름
从最后一个非叶结点开始进行调整
发表于 2018-10-19 09:31:26 回复(0)
xxxxxxxxxxxxxxxa头像 xxxxxxxxxxxxxxxa
可以检查每个选项是否满足最大堆性质来求解，
也可以使用O(N)的下渗建堆方式求解，N/2的节点开始下渗直到N=1;
发表于 2018-06-14 16:42:56 回复(0)
布丁🍮头像 布丁🍮
堆排序第一步：把最后一个节点元素和根节点元素对换位置。
发表于 2017-08-24 17:15:06 回复(0)
Bacchuc头像 Bacchuc
此题先将题目列为完全二叉树，然后从最后一个非叶子节点开始，将其与左右两子节点比较，将最小的和父节点交换并满足堆规则，一次类推得到初排序…
发表于 2017-04-03 16:42:48 回复(0)
DannyZhao头像 DannyZhao
http://blog.csdn.net/morewindows/article/details/6709644
发表于 2017-03-02 16:04:07 回复(0)
程式猎人头像 程式猎人
从最后一个非终端节点开始调整啰
发表于 2016-08-31 09:33:20 回复(0)
牛客617177号头像 牛客617177号
从堆里面的最后一个非叶子节点开始调整，使得它符合堆的性质
发表于 2016-06-20 21:10:56 回复(0)
提交观点

问题信息

堆
来自：阿里巴巴2017实习生...
难度：
20条回答 21336浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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