algorithm - 第 k 个最小元素的最大堆与最小堆

Question

我无法理解为什么寻找第 k 个最小元素的解决方案使用最大堆方法。对于第 k 个最大的元素，采用最小堆方法。使用 min heap 查找第 k 个最小元素不是更有意义吗，因为最小元素将始终是根元素？因此，如果我们想找到第三小的元素，那么我们只需删除根 2 次，构建堆，就可以得到第三小的元素。在最大堆中，最小的不在根，那么为什么使用它更好呢？对数组中的升序或降序进行排序也是如此。我看到大多数人使用最大堆来提升。

Answer 1

事实上，我们可以同时使用 Min 和 Max heap 来找到第 k 个最小的元素：

1. 就像您描述的那样，我们可以构建一个最小堆，然后在循环中提取第 k 个元素。

或者

2. 我们可以只用 k 个元素构建 Max Heap。然后我们只需将其余元素与根进行比较，仅将小于根的元素替换为根，因此最大堆总是有 k 个最小的元素。