查找数组中的 K 个最小值（堆 vs QuickSelect）

假设我们有一个数组，我们希望找到它的 K 个最小值：

有两种方法：

1.使用快速选择算法（O(n)时间复杂度和O(1)空间）

2.使用最小堆数据结构（O(NlogK)时间复杂度和O(K)空间）

我想知道什么时候一个比另一个更受青睐。

我想这两个都可以分发。

检查这个out http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html:-

比排序或堆更快的选择

由于对整个数据集进行排序非常慢，因此选择 前 K 个项目，并仅对少数“顶部”元素进行排序，给出 当整个数据集在她页面排序时给用户留下的印象 通过结果集。这将给出 O(k*log(k) + n) 与 O(n*log(n)) 相反，如果 K 合理，则速度要快得多 小（例如几百）。

另一种方法是使用堆并不断弹出 最小的数字，同时放回较大的数字，因为我们收到了 N 数字作为流。这适用于 O(n*log(K)) 运行时间，如下所示 堆包含 K 个元素，因此当我们测试 N 时，高度为 log(K) 总数，尽管预计运行时间大于 快速选择和排序组合。