已知小根堆为 8,15,10,21,34,16,12,删除关键字 8 之后需重建堆,在此过程中,关键字之间的比较次数是()。
A.1
B.2
C.3
D.4
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
第一步:堆顶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不需要交换位置,这是第三次比较 。
我尼玛把8放下去以后,自己又把8比较了
删除根节点8后,将最后一个结点12代替它的位置,然后开始调整。
向下调整:比较12和其子节点15和10【12与15比较】【12与10比较,并互换】
比较12与其子节点16【12与16比较,结果小于,无剩余子节点】
调整结束,比较3次。
补充 根结点 使用 最后一个元素
删除根结点用最后一个叶子结点补充,与左右孩子进行比较,此时将12与10互换,再对进行互换的12与更下层的左右孩子比较
解答:
删除8后,用小根堆最...
登录后提交答案