arrays - 在数组中查找 K 个最小值(堆与 QuickSelect)

Question

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

有两种方法:

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

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

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

我想它们都可以分发。

Answer 1

检查这个 out :-

Quick select than sorting or heap

As sorting the whole dataset is quite slow, it makes sense to select the top K items and sort only that few ‘top’ elements giving the impression to the user as the whole dataset was sorted as she pages through the result set. This will give a running time of O(k*log(k) + n) as opposed to O(n*log(n)) which is much faster if K is reasonably small (few hundreds for example).

An other approach would be to work with a heap and keep popping the smallest number while putting back a larger as we are receiving the N numbers as a stream. This would work with O(n*log(K)) running time as the heap holds K elements so the height is log(K) while we test N numbers in total, although it’s expected running time is larger than the quick select and sort combination.