是否有任何算法可以在O（log n）时间内找到最大堆中的第k个最小元素？

Question

在最坏的情况下，第k个最小的元素可能位于最大堆的最后一级。在那种情况下，找到元素所需的时间可能会达到O（n），因为在元素中可能有n / 2个元素。最坏的情况是在堆的最后一级。要么是否有其他算法可以在O（logn）时间中找到MAX堆中的第k个最小元素？

n =否。堆中的元素数

Answer 1

是。您可以在O（k log n）中执行此操作。为了说明该过程，请考虑一个示例数组[30,20,10,9,7,5]。

为此的堆结构由：

现在，我们有以下模式。

• 第一个最小元素->第六个最大元素
• 第二个最小元素->第五个最大元素
• 第3个最小元素->第4个最大元素
• ..
• ..
• ..
• 第k个最小元素->第（n-k + 1）个最大元素

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