Get the k-largest elements from an array whit n Elements, where n is much larger than k

Question

Suppose you have an unsorted array of length n. Now you want to take the k-largest elements from the array. We also know that n is much larger than k.

My naive idea is to sort the array and output the k-largest elements. That would cost O(nlog(n)). Is there a more efficient algorithm that takes advantage of the fact that n is much larger than k ?

Possible duplicate of [In an integer array with N elements , find the minimum k elements?](https://stackoverflow.com/questions/12057195/in-an-integer-array-with-n-elements-find-the-minimum-k-elements) — Alex M, Nov 09 '18 at 18:23

score 4 · Answer 1 · answered Nov 09 '18 at 18:17

Yes, more effective algorithms do exist.

Get k first elements, build min-heap containing these k elements.

Traverse through other elements. If current item is larger than heap top, remove top and insert current item.

After the end heap will contain k largest elements.

Complexity is O(N*logK)

Also consider QuickSelect algorithm with average time O(n) (while it has worst case up to quadratic)

Get the k-largest elements from an array whit n Elements, where n is much larger than k

1 Answers1