algorithm - 有没有找到第k大元素的 "tournament"算法？

Question

我知道我们可以在 N+log(N)-2 中找到大小为 N 的数组中的 2 最大元素，使用一场“锦标赛”algorithm .现在我想知道我们是否可以使用类似的“锦标赛”找到第 k 个 最大的元素。

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

请问有没有其他方法。

Answer 1

我相信你可以使它成为一个 O(N log k) 算法:遍历数组，并维护最大 k 的最小堆 目前遇到的元素。所以第一个 k 元素直接进入堆。每个后续元素都将与堆的尖端进行比较，如果它更大，尖端将从堆中移除并插入新元素，这是一个 O(log k) 操作一个大小为 k 的堆。当算法完成后，序列的长度至少为 k，那么堆的顶端将具有第 k 个最大的元素，其余的堆放较大的元素。

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