题目
【0、2、1、4、3、9、5、8、6、7】是以数组形式存储的最小堆,删除堆顶元素0后的结果是()
A.【2、1、4、3、9、5、8、6、7】
B.【1、2、5、4、3、9、8、6、7】
C.【2、3、1、4、7、9、5、8、6】
D.【1、2、5、4、3、9、7、8、6】
解答
正确答案是 D
首先,题目有问题,[0,2,1,4,3,9,5, 8 ,6,7], 原数组是这样才对得上号。
第二,堆是一种经过排序的完全二叉树,最小堆:根结点的键值是所有堆结点键值中最小者。根据这个不难写出原来堆依次为 顶层0 第二层 2 1 第三层 4 3 9 5 第四层 8 6 7
第三,最小堆删除堆顶后,用最后一个元素暂代堆顶,然后变成顶层7 第二层 2 1 第三层 4 3 9 5 第四层 8 6 ,7>2>1,故1和7对调,对调后顶层1 第二层 2 7 第三层 4 3 9 5 第四层 8 6;因为9>7>5,5和7对调 ,对调后 顶层1 第二层 2 5 第三层 4 3 9 7 第四层 8 6;形成新的最小堆
故答案为:D
看这个冲刺面试