在数组中查找 K 个最小值(堆与 QuickSelect) [英] Finding K smallest values in an array (Heap vs QuickSelect)

问题描述

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

Let's assume that we have an array and we wish to find K smallest values of it :

有两种方法:

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

1.Using quick select algorithm (O(n) time complexity and O(1) space)

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

2.Using min heap data structure (O(NlogK) time complexity and O(K) space)

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

I'd like to know when one is preferred over another one.

我想它们都可以分发.

推荐答案

检查这个 out:-

快速选择而不是排序或堆

由于对整个数据集进行排序很慢，因此选择前 K 个项目并仅对少数顶级"元素进行排序，从而给出给用户的印象是整个数据集在她翻页时进行了排序通过结果集.这将给出 O(k*log(k) +n) 与 O(n*log(n)) 相反，如果 K 是合理的，O(n*log(n)) 会快得多小(例如几百个).

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).

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

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.

这篇关于在数组中查找 K 个最小值(堆与 QuickSelect)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！