Finding the first n largest elements in an array

Question

I have got an array containing unique elements. I need to find out the first n largest elements in the array in the least complexity possible. The solution that I could think of so far has a complexity of O(n^2).

    int A[]={1,2,3,8,7,5,3,4,6};
    int max=0;
    int i,j;
    int B[4]={0,0,0,0,};//where n=4;
     for(i=0;i<A.length();i++)
       {
         if(A[i]>max)
          max=A[i];
       }
     B[0]=max;
     for(i=1;i<n;i++){
       max=0;
       for(j=0;j<A.length();j++){
         if(A[j]>max&&A[j]<B[i-1])
            max=A[j];
       }
        B[i]=max;
     }

Please, if anyone can come up with a better solution which involves less complexity, I will be highly grateful. And I don't intend to change the original array!!

Answer 1

Find the kth biggest element, using selection algorithm.
Next, iterate the array and find all elements which are larger/equal it.

complexity: O(n) for selection and O(n) for iterating, so the total is also O(n)

Answer 2

The usual trick to select the n largest elements is to maintain a min-priority queue.

• Unconditionnally insert into the queue the n first elements
• For each remaining element x, insert x if it is greater than the least element of the queue (O(log n) operation), and remove the least element (O(log n)).
• When done, the priority queue contains n elements, which are the n largest elements of the original array.

Total complexity: O(N log n) where N is the total number of elements in the array.

I leave to you as an exercise the implementation details (first step is to learn about priority queues, and implement one).