我有一个关于使用最小堆查找第 k 个最大元素的问题。算法如下:
我们取前 k 个元素并构建一个 minheap
令 Sk 为 S 中的最小元素。
从剩余的 nk 个元素中看一个新元素。
如果新元素大于 Sk,则将其替换到 S 中,并对堆进行重新排序。
S 然后将有一个新的最小元素。
在查看了所有其他元素之后,Sk 就是答案
我不明白这个算法。例如,让数字为 1、2、3、4。我们想找到第 4 个最大的,即 4。但是当我们使用算法时,我们取前 4 个元素,构建 minheap,Sk 为 1。
我究竟做错了什么?如果有人可以提供帮助,我将不胜感激。谢谢