已知关键字序列 28, 22, 20, 19, 8, 12, 15, 5是大根堆(最大堆),对该堆进行两次删除操作后,得到的新堆是( )。
A. 20, 19, 15, 12, 8, 5
B. 20, 19, 15, 5, 8, 12
C. 20, 19, 12, 15, 8, 5
D. 20, 19, 8, 12, 15, 5
要解决这个问题,需明确大根堆的结构...
用户登录可进行刷题及查看答案
要解决这个问题,需明确大根堆的结构及删除操作的流程。大根堆中每个父节点的值均大于或等于其子节点的值,删除操作通常是移除堆顶元素(最大值),将最后一个元素移至堆顶,再通过向下调整维持堆的性质。以下是两次删除操作的详细步骤:
初始大根堆数组
原序列:[28, 22, 20, 19, 8, 12, 15, 5] 对应完全二叉树结构(根节点为 28,按数组索引顺序存储)。
[28, 22, 20, 19, 8, 12, 15, 5]
第一次删除操作
删除堆顶元素 28,将最后一个元素 5 移至堆顶,得到临时数组:[5, 22, 20, 19, 8, 12, 15]。
[5, 22, 20, 19, 8, 12, 15]
向下调整堆顶 5:
堆顶 5 的左孩子为 22(索引 1),右孩子为 20(索引 2),最大子节点为 22,交换 5 和 22,数组变为:[22, 5, 20, 19, 8, 12, 15]。
[22, 5, 20, 19, 8, 12, 15]
此时节点 1(值为 5)的左孩子为 19(索引 3),右孩子为 8(索引 4),最大子节点为 19,交换 5 和 19,数组变为:[22, 19, 20, 5, 8, 12, 15]。
[22, 19, 20, 5, 8, 12, 15]
调整完成,第一次删除后的堆为:[22, 19, 20, 5, 8, 12, 15]。
第二次删除操作
删除堆顶元素 22,将最后一个元素 15 移至堆顶,得到临时数组:[15, 19, 20, 5, 8, 12]。
[15, 19, 20, 5, 8, 12]
向下调整堆顶 15:
堆顶 15 的左孩子为 19(索引 1),右孩子为 20(索引 2),最大子节点为 20,交换 15 和 20,数组变为:[20, 19, 15, 5, 8, 12]。
[20, 19, 15, 5, 8, 12]
此时节点 2(值为 15)的左孩子为 12(索引 5),15 > 12,无需调整。
调整完成,第二次删除后的堆为:[20, 19, 15, 5, 8, 12]。
最终答案
对比选项,正确结果为: B. 20, 19, 15, 5, 8, 12
登录后提交答案
暂无评论,来抢沙发