使用最小堆查找第 k 大元素

Question

我有一个关于使用最小堆查找第 k 大元素的问题。算法如下：

1. 我们取出前 k 个元素并构建一个最小堆

2. 设 Sk 为 S 中最小的元素。

3. 从剩余的 nk 元素中查看一个新元素。

4. 如果新元素大于 Sk，则将其替换到 S 中，并对堆重新排序。

5. 然后 S 将有一个新的最小元素。

6. 看完所有其他元素后，Sk就是答案

我不明白这个算法。例如，让数字为1,2,3,4。我们想要找到第四大的，即4。但是当我们使用该算法时，我们取前4个元素，构建minheap，Sk为1。

我究竟做错了什么？如果有人可以提供帮助，我将不胜感激。谢谢

Answer 1

我认为您的困惑在于术语。序列 1, 2, 3, 4 中最大的元素是数字 4。第二大元素是 3，第三大元素是 2，第四大元素是 1。由于算法返回 1，因此它工作正常。

然而，4 是序列中第 k 个最小的元素。如果您想找到第 k 个最小元素，只需将最小堆与最大堆交换，并对算法进行适当的调整即可。

希望这可以帮助！