arrays - 在数组中查找 K 个最小值（Heap vs QuickSelect）

Question

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

有两种方法：

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

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

我想知道什么时候一个比另一个更受欢迎。

我想它们都可以分发。

Answer 1

看看这个： -

比排序或堆快速选择

由于对整个数据集进行排序非常慢，因此选择前 K 个项目并仅对给用户印象的少数“顶级”元素进行排序是有意义的，因为整个数据集是在她翻阅结果集时进行排序的。这将给出 O(k*log(k) + n) 的运行时间，而不是 O(n*log(n)) 如果 K 相当小（例如几百个），则运行时间要快得多。

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