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

Question

我很难理解为什么找到第k个最小元素的解决方案使用最大堆方法。对于第k个最大元素，使用最小堆方法。使用最小堆来查找第k个最小元素是否更有意义，因为最小元素将始终是根？因此，如果要查找第3个最小的元素，则只需删除根两次，构建堆，然后得到第3个最小的元素。在最大堆中，最小不是根，那么为什么更好使用呢？对于数组中的升序或降序排序也是如此。我看到大多数人使用最大堆来提升。

Answer 1

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

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

或者

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