是否有“锦标赛”算法可以找到第 k 个最大元素？

Question

我知道我们可以使用“锦标赛”算法在大小数组中找到第二大元素。现在我想知道我们是否可以使用类似的“比赛”找到第k 个最大的元素。NN+log(N)-2

我知道有一个O(N)“选择”算法可以找到第k 个最大的元素。它Quick Select与“好”枢轴一起使用，可以在O(N). 我们还可以heap从数组中构建 a 并从 中O(N)检索k元素heap。

我想知道是否有另一种方法。

Answer 1

我相信你可以将其设为 O( N log k ) 算法：迭代数组，并维护迄今为止遇到的最大k元素的最小堆。所以前k个元素直接进入堆。每个后续元素都将与堆的尖端进行比较，如果它更大，则将从堆中删除尖端并插入新元素，对于大小为k的堆，这是一个 O(log k ) 操作。当算法完成时，并且序列的长度至少为k，则堆的尖端将具有第k个最大的元素，而堆的其余部分将具有较大的元素。

这种方法的最坏情况行为比中位数 O( n ) 解决方案要差，但更容易实现，并且对于较小的k会产生相当好的行为。因此它可能非常适合许多实际应用。