有没有算法可以在O(log )时间内找到最大堆中的第k个最小元素？

Question

在最坏的情况下，第k个最小的元素可能在最大堆的最后一层。在这种情况下，查找该元素所需的时间可能会达到O(n)，因为在最坏的情况下，堆的最后一层可能有n/2个元素。或者有没有其他算法可以在O(logn)时间内找到最大堆中的第k个最小元素？

N=否。堆中元素的数量

Answer 1

是。你可以在O(k log n)中做到这一点。为了解释该过程，请考虑一个示例数组[30,20,10,9,7,5]。

它的堆结构是这样给出的：

​

​

现在，我们有了以下模式。

• 第1个最小元素->第6个最大元素
• 第2个最小元素->第5个最大元素
• 第3个最小元素->第4个最大最小元素-> (n-k+1)第4个最大元素

例如，在我们的示例中，第5个最小元素->第2个最大元素-> 20