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

Question

5

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

1. 取前k个元素并构建小根堆 2. 令Sk为S中最小元素 3. 查看新元素，从剩余的n-k个元素中选择 4. 如果新元素比Sk大，则用它替换Sk，并重新排序堆 5. S将会有一个新的最小元素 6. 在查看所有其他元素之后，Sk就是答案

我不理解这个算法。例如，我们有数字1、2、3、4。我们想找到第4个最大的元素，即4。但当我们使用该算法时，我们取前4个元素构建小根堆，并且Sk是1。

我做错了什么？如果有人能帮忙解答，我会很感激。谢谢。

- user1941394

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

我认为你的困惑在于术语。在序列1、2、3、4中，最大的元素是数字4。第二大的元素是3，第三大的元素是2，第四大的元素是1。由于算法返回1，因此它运行正确。

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

希望这能帮助你！