CODEWITHSUNDEEP
c++arraysmaxmin
Jack Smother
Jack Smother

Reputation: 207

Getting top 50 highest numbers from an unsorted array efficiently

Assuming we have a large data set in an array (say 50000) and we now want to get the top 50 highest numbers in the array, Would you suggest using a priority queue and pop 50 times? inserting each of the 50000 elements from the array to the priority queue can take up to O(n) and if you do it 50000 times it becomes O(n^2) which is expensive. How do I get a better O complexity?

Upvotes: 3

Views: 922

Answers (1)

i Code 4 Food
i Code 4 Food

Reputation: 2154

You can use nth_element to find the top 50 elements with average complexity ~O(n), and then sort the 50 initial indexes of the array if you need.

Or, you can iterate through the array, placing items into a separate priority_queue as long as you have less than 50 elements, or the current item is higher than the 50th element. Whenever you have 51 elements, you pop one out. Worst case O(n*log(50)).

One last thing, if all the values in the array are below a certain limit, for example <= 10^5, you can use Bucket sort. Simply iterate through the whole array, and do ++bucket[array[i]];. Then you iterate linearly on bucket taking note of the 50 smallest numbers you find. Worst case O(n) + O(m) where m = maximum value in the array.

Upvotes: 4

Related Questions