搜索最大堆中的第7个最大元素？

Question

所以我和我的朋友在这个问题上没有一致的看法.它要求在n个元素的最大堆中搜索第7个最大元素的时间复杂度？

我认为它应该是O(n)并且她认为它应该是O(1).我的逻辑是假设n是7然后第7个最大元素将是堆中的最后一个元素,所以如果我们考虑最坏的情况它应该是O(n).然而她说,因为它是最大堆,所以找到第7大元素应该花费不变的时间.但是使用她的逻辑甚至可以在O(1)时间内找到第50大元素或第100大元素.我们遇到这个问题的书也说解决方案是O(logn).

有人可以告诉我哪种解决方案是正确的？

Answer 1

找到最大堆中第七大元素的简单算法是

repeat 6 times:
    del-max(heap)
return max(heap)

第一个循环执行恒定数量的del-max操作,每个操作花费O(lg n)时间.该max操作需要恒定的时间.该del-max业务占主导地位,导致总O(LG ñ)的复杂性.我并不是说这是最优的.