4

我有一个关于使用最小堆查找第 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。

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

4

1 回答 1

4

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

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

希望这可以帮助!

于 2013-01-12T21:08:29.750 回答