data-structures - 在最大堆中找到 logn th 最大值的最有效方法

Question

标题说明了一切; 在具有n 个元素的最大堆中找到第n个最大数的最有效方法是什么？ps：我正在阅读的教科书含糊地解释了一个具有时间复杂度的解决方案，即使用另一个我无法理解的堆，我们能做得更好吗？
O(lognloglogn)

Answer 1

让我们H成为原始的最大堆。让H'另一个最大堆，最初是空的，它对(index, value)来自第一个堆的元素对进行操作，并根据第二个组件对这些元素对进行排序。

1. H'.push(0, H[0])
2. count = ceil(log n)
3. while count > 0 do
   4. (i, v) := H'.extract-max()// 需要O(log log n)时间
   5. H'.push(2i+1, H[2i+1])如果H[2i+1]存在 //O(log log n)时间
   6. H'.push(2i+1, H[2i+2])如果H[2i+2]存在 //O(log log n)时间
   7. count := count - 1
4. 返回v

我们O(log log n)对 的 操作的运行时间有限制的原因H'是它H'最多包含log n元素，并且每个操作在时间上与堆的元素数量成对数，即O(log log n).

总运行时间明显O(log n log log n)。我假设原始的最大堆H用数组表示。