已知小根堆为 8,15,10,21,34,16,12,删除关键字 8 之后需重建堆,在此过程中,关键字之间的比较次数是()。
A.1
B.2
C.3
D.4
删除根节点8后,将最后一个结点12代替它的位置,然后开始调整。
向下调整:比较12和其子节点15和10【12与15比较】【12与10比较,并互换】
比较12与其子节点16【12与16比较,结果小于,无剩余子节点】
调整结束,比较3次。
补充 根结点 使用 最后一个元素
删除根结点用最后一个叶子结点补充,与左右孩子进行比较,此时将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。
登录后提交答案