algorithm - 在 O(n) 时间内查找 log n 个最大条目

Question

有没有办法在 O(n) 时间内找到包含 n 个元素的数组中的 log n 个最大元素？

我将创建一个基于数组的 HeapPriorityQueue，因为如果所有元素都可用，则可以使用自下而上的堆构造在 O(n) 时间内创建堆。那么删除这个优先级队列的第一个元素应该在 O(1) 时间内，不是吗？

Answer 1

Then removing the first element of this priority queue should be in O(1) time isn`t?

这将是O(logn)，因为您还删除了第一个元素。不删除就看它是O(1)。重复此删除 logn 次将是 O(log^2(n))，仍然是 O(n)，所以这个解决方案确实可以满足要求。

另一个选择是使用 selection algorithm直接找到log(n)的最大元素，这也是O(n)。