algorithm - 在最大堆中搜索第 7 大元素？

Question

所以我和我的 friend 在这个问题上意见不一致。问在n个元素的最大堆中寻找第7大元素的时间复杂度？

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

谁能告诉我哪个解决方案是正确的？

Answer 1

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

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

第一个循环执行固定数量的 del-max 操作，每个操作花费 O(lg n) 时间。 max 操作需要常数时间。 del-max 操作占主导地位，导致总复杂度为 O(lg n)。我并不是说这是最佳的。