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

Question

标题说明了一切；在具有 n 个元素的最大堆中找到第 log 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. return v

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

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