Finding K smallest values ​​in an array (Heap vs QuickSelect)

Question

Suppose we have an array and we want to find K its smallest values:

There are two approaches:

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

2. Using a minimal heap data structure (O (NlogK) and O (K) time complexity)

I would like to know when someone prefers another.

I think both of them can be distributed.

Answer 1

Note out : -

A quick choice than sorting or heap

Since sorting the entire data set is rather slow, it makes sense to select the top K elements and sort only those few "top elements that give an impression to the user, since the entire data set was sorted by its pages through the result set. This will give O (k * log (k) + n) as opposed to O (n * log (n)), which is much faster if K is reasonably small (for example, a few hundred).

Another approach would be to work with the heap and keep popping up the smallest number while returning the bigger one, since we get N numbers as a stream. This will work with O (n * log (K)) runtime, as the heap contains K elements, so the height of log (K) while we check N as a whole, although the expected runtime is longer than the combination of quick selection and sorting.