堆实现.最糟糕的案例提取复杂性

Question

嗨,我正在学习使用python的算法.我正在阅读本书中的一些示例问题,其中要求说明为什么在作为数组实现的堆上的提取操作的最坏情况时间为O(log n)？我不知道从哪里开始,我正在接近考试.有人可以帮我证明一下吗？谢谢

Answer 1

假设我们有一个最大堆.我将说明n = 7,但逻辑是相同的更大尺寸的堆.

当根节点被更改为包含所有节点的最小值时,我们会发生最糟糕的提取情况(我们在O(1)中提取根并将数组中的最后一个元素作为根).

现在,当我们在根上调用Max-Heapify时,该值必须与其子级在每个级别进行交换,直到达到最低级别.

这是因为,在每次交换之后,该值仍将小于其子节点(因为它是最小值),直到它达到其不再有子节点的最低级别.

在这样的堆中,最大化根的交换次数将等于树的高度,即log(n).因此,最坏的情况是运行时间为O(log n).