首页 > 试题广场 >

已知小根堆为8,15,10,21,34,16,12，删除关键

[单选题]

已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，最后的叶子节点为

查看答案及解析

2113301012-傅励瑶

建好堆后8是作为的堆顶元素，如果删除8，把整颗已经建好的堆的最后一个元素(12)和8交换，然后在自上而下地进行调整（就是比较根节点和左右节点，如果有比根节点更小的就交换，然后就可以得到以元素16最为最后一个元素的堆）

发表于 2020-02-14 22:10:41 回复(0)

褪涩

发表于 2019-09-14 20:17:05 回复(5)

阿兰图灵的小绿人

答案选C

1，删除关键字8后将最后一个叶子结点关键字12挪动到执行删除操作后空缺的位置。（为什么要挪动最后一个数：堆一定是完全二叉树结构，如果挪动其他叶子节点，最后得到的那一坨就不是堆了）

2，根据大顶堆大的数上浮，小顶堆大的数下沉的原则，12应下沉至比她小的右孩子位置，此时做交换操作。（即使左右孩子是非空叶子节点也是要参与比较的）

3，继续和左右孩子对比，不满足下沉条件，调整结束。此时该堆为全新的小顶堆，最后一个关键字为16。

发表于 2021-08-05 14:05:39 回复(0)

LukeSu

被删除元素一定是用堆底替代的，因为堆是一个完全二叉树，故把12拿上去填补8的位置。接下来进行“下沉”操作：

“下沉”就是该结点不断与其孩子结点中较小的一个进行比较，若比孩子结点中较小的一个结点还要小，就交换。

于是过程如下：

1、首先比较12的孩子结点，即15和10，得到一个更小的结点是10。 //比较次数+1

2、接着用12和孩子结点中较小的那个比较，即12和10比较，12>10，交换结点。//比较次数+1

3、最后一层就一个结点16，所以直接拿来和12比较，12<16，不用交换。 //比较次数+1

所以比较次数为3次，最后的结点为16。

编辑于 2023-09-05 12:09:51 回复(0)

天尊墨宇

选C删除8之后，将12移动到堆顶，第一次15和10比较，第二次12和10比较，完了之后交换，第三次12和16比较，一共比较了3次

编辑于 2020-07-18 11:10:27 回复(1)

提交观点

问题信息

堆

上传者：城市里的养猫者

难度：

5条回答 403收藏 18689浏览

扫一扫，把题目装进口袋