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

Question

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

1. 我们取前 k 个元素并构建一个 minheap

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

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

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

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

6. 在查看了所有其他元素之后，Sk 就是答案

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

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

Answer 1

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

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

希望这可以帮助！