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