首页 > 试题广场 >

有组记录的排序码为(46,79,56,38,40,84),则

[单选题]
有组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为【 】
  • 79,46,56,38,40,80
  • 84,79,56,38,40,46
  • 84,79,56,46,40,38
  • 84,56,79,40,46,38
推荐
选B。堆排序是基于最大堆来实现的。
  1. 将待排序的数据看作一棵完全二叉树,将第一个数据作为二叉树的根,从左至右依次填充二叉树。
  2. 对这棵完全二叉树进行调整建堆,即父节点不小于两个子节点为原则
  • 重建堆:将根节点46移出作为待调整节点,然后对根节点的左右子树重建堆。根据得出的树图来看左子树不变,右子树84和56交换位置。
  • 从84和79选择较大的84同待调整的46做比较,将84上移到根节点。
  • 将56和待调整的46做比较,56上移到空节点处,46移到56位置处。
所以最终的初堆序列为:84,79,56,38,40,46
编辑于 2019-07-05 15:34:50 回复(2)
堆:最大堆、最小堆 最小堆:每个子树根节点值小于其子节点的完全二叉树 最大堆:每个子树根节点值大于其子节点的完全二叉树
发表于 2022-01-27 18:27:54 回复(0)
感觉答案是84,46,79,38,40,56
发表于 2022-07-08 08:58:23 回复(3)
堆排序就是构造一个大顶堆
发表于 2022-02-15 09:18:20 回复(0)
利用堆排序建立初始堆有两种办法,第一种是先把排序码组成树,再依次比较n/2处的节点与其子节点中较大(小)值中其中一个的大小(这里得看题目中要求你建成大根堆还是小根堆),最后得到结果。这题需要用这种方式得到选项中的b答案。 -----------------------------如果是第二种方法,也就是依次向堆中插入元素,在插入过程中做调整。这种做法得到的大根堆为84,46,79,38,40,56
发表于 2022-07-11 10:23:21 回复(1)
B 交换:84 56 84 46 56 46
发表于 2017-12-12 14:15:21 回复(1)
换成大顶堆
发表于 2023-09-09 23:45:17 回复(0)
46,79,84,38,40,56 46,79,84,38,40,56 84,79,56,38,40,46
发表于 2023-03-23 01:26:06 回复(1)
初步构造大顶堆是从左到右 从上到下
发表于 2022-10-14 15:09:02 回复(0)