我有一个关于使用最小堆查找第 k 大元素的问题。算法如下:
我们取前 k 个元素并构建一个最小堆
设Sk为S中的最小元素。
从剩余的 n-k 个元素中寻找一个新元素。
如果新元素大于 Sk，则将其替换到 S 中，并对堆重新排序。
然后 S 将有一个新的最小元素。
在查看所有其他元素后，Sk 就是答案
我不明白这个算法。例如，让数字为 1、2、3、4。我们想找到第 4 大的，也就是 4。但是当我们使用算法时，我们取前 4 个元素，构建最小堆，Sk 为 1。
我做错了什么？如果有人可以提供帮助，我将不胜感激。谢谢
最佳答案
我认为您对术语感到困惑。序列 1, 2, 3, 4 中最大的元素是数字 4。第二大元素是 3，第三大元素是 2，第四大元素是 1。由于算法返回 1，因此它可以正常工作.
但是，4 是序列中第 k-最小 元素。如果你想找到第 k 个最小的元素，你可以将最小堆与最大堆交换，并对算法进行适当的调整。
希望这对您有所帮助!
关于algorithm - 使用最小堆查找第 k 个最大元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14297912/