已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键_

返回主页

[数据结构 P1557] 已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键

学习人数: 5.0k

正确率: 55%

答案解析

题目描述

未通过

已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。

A．1

B．2

C．3

D．4

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

上一题

下一题

加入错题本

个人笔记

已有24条笔记

登录后提交答案

5 个回答 (点击展开回答)

史迪仔

2025年4月10日 20:17

第一步：堆顶12要和其左右子节点中较小值比较，12的左右子节点是15和10，10小于15 ，所以12先和10比较。因为12大于10，所以12和10需要交换位置，这是第一次比较。

○ 第二步：交换后，12到了原来10的位置，此时12又有了新的左右子节点16和12（原12的右子节点），12的新左右子节点中较小值是12（自身），12和12不需要交换位置，但这也算是一次比较，这是第二次比较。

○ 第三步：接着看交换后原来12位置（现在是10），其左右子节点是16和12 ，12小于16 ，10要和12比较，10小于12不需要交换位置，这是第三次比较。

小灰机

2024年11月9日 21:28

我尼玛把8放下去以后，自己又把8比较了

Djiangxu

2024年9月17日 15:52

删除根节点8后，将最后一个结点12代替它的位置，然后开始调整。

向下调整：比较12和其子节点15和10【12与15比较】【12与10比较，并互换】

比较12与其子节点16【12与16比较，结果小于，无剩余子节点】

调整结束，比较3次。

Austin00

2024年8月21日 15:18

补充根结点使用最后一个元素

17679377259

2024年7月20日 16:13

删除根结点用最后一个叶子结点补充，与左右孩子进行比较，此时将12与10互换，再对进行互换的12与更下层的左右孩子比较

参考答案

解答：

删除8后，用小根堆最...

用户登录可进行刷题及查看答案

解答：

删除8后，用小根堆最后一个元素占位，然后需要维护堆的性质，设根结点下标为1，调用MIN-HEAPIFY(A, 1)，MIN-HEAPIFY伪代码如下：

MIN-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ A.heap-size and A[l] < A[i]
        smallest = l
    else smallest = i
    if r ≤ A.heap-size and A[r] < A[smallest]
        smallest = r
    if smallest ≠ i
        exchange A[i] with A[smallest]
        MIN-HEAPIFY(A, smallest)

总共发生3次比较。

本题选C。