kth最小元素的Max堆与Min堆

Question

我很难理解为什么查找kth最小元素的解决方案使用Max堆方法。对于kth最大元素，则采用最小堆方法。使用min堆查找kth最小元素不是更有意义吗，因为最小的元素总是根元素？因此，如果我们想找到第三个最小的元素，那么我们只删除根2次，构建堆，然后得到第三个最小的元素。在最大堆中最小的不是根，那么为什么使用它更好呢？数组中的升序或降序排序也是如此。我看到大多数人使用最大堆来提升。

Answer 1

实际上，我们可以使用Min和Max堆找到k个最小元素：

1. 正如您所描述的，我们可以构建一个Min堆，然后在循环中提取k元素。

或

1. 我们只需k个元素就可以建立最大堆。然后，我们将剩下的元素与根进行比较，用根元素代替小于根的元素，因此Max堆总是有k个最小的元素。