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

Answer 3

You can do this in O(n) if your elements are integers (or any integral type) within a range, i to k inclusive with k >= i. With this constraint, you can apply "bucket sort" to this.

The idea is quite simple. Allocate k - i + 1 buckets. Now, iterate through your collection and increment the bucket for that integer. Then, at the end, you can "recreate" the sorted list by creating as many integers that were found (i.e. the bucket number).

For example,

int collection[] = { 10, 4, 7, 1, 9, 0, 12 }; // maximum value to expect is 12, minimum is 0
int buckets[ 13 ] = { 0 };

for( int i = 0; i < 13; i++ )
{
      int n = collection[ i ];
      buckets[ n ]++;
}


// the first n largest elements (n = 4)

for( int j = 12; j >= 12 - 4; j-- )
{
      int n = buckets[ j ];

      while( n > 0 )
      {
           printf( "%d ", j );
           n--;
      }
}
printf( "\n" ); 

Answer 4

You can use a Priority Queue using Heap (maxHeap) to solve this. Perform heap n times to get the first n largest elements. Each Heap operation takes O(log N) time, so N heap operations would result in O(N log N) time.

Answer 5

Use a modified version of Quick Sort. You do not need to actually sort the whole array. You only need to partition N elements larger than the pivot value. For more information, please read Introduction to Algorithms.

Answer 6

I don't believe on this but you could also create a heap out of it in O(n). And then just remove the root k number of times and heapify the heap for k largest numbers. In this way for each largest numbers it will cost you log(n).

public class HeapSort1{                                                          
    public static void main(String args[]){                                  
            int[] array={5,75,1,5,4,1,2,4,8,4,2,15,4,2,1,5,779,9,1};         
            int heapsize=array.length-1;                                     
            for(int i=heapsize/2;i>=0;i--){                                  
                    maxHeapify(array,i,heapsize);                            
            }                                                                
            for(int i=heapsize;i>0;i--){                                     
                    array[i]=array[0]+array[i];                              
                    array[0]=array[i]-array[0];                              
                    array[i]=array[i]-array[0];                              
                    maxHeapify(array,0,--heapsize);                          
            }                                                                
            printArray(array);                                               
    }                                                                        
    public static void maxHeapify(int[] array,int i,int heapsize){           
            int largest=i;                                                   
            int left=2*i+1;                                                  
            int right=2*i+2;                                                 
            if(left<=heapsize && array[left]>array[i]){                      
                    largest=left;                                            
            }                                                                
            if(right<=heapsize && array[right]>array[largest]){              
                    largest=right;                                           
            }                                                                
            if(largest!=i){                                                  
                    array[i]=array[largest]+array[i];                        
                    array[largest]=array[i]-array[largest];                  
                    array[i]=array[i]-array[largest];                        
                    maxHeapify(array,largest,heapsize);                      
            }                                                                
    }                                                                        
    public static void printArray(int[] array){                              
            System.out.print("\n [");                                        
            for(int i=0;i<array.length;i++){                                 
                    System.out.print(array[i]+" ");                          
            }                                                                
            System.out.print("] \n");                                        
    }  
    public static int getMax(){
            int max=array[0];
            array[0]=array[heapsize];
            maxHeapify(array,0,--heapsize);
    }

 }                                                                                                                                                             

Answer 7

I tried this as per @Alexandre C.

This gets the top 10 items of a unbounded input. It breaks after it processed 20 items from the input.

import random
import time
top_10_items = []
cnt = 1
while True:
    rand = random.randint(1,100)
    print(rand)

    time.sleep(1)
    if len(top_10_items) !=10:
        top_10_items.append(rand)
    else:
        m = min(top_10_items)
        if rand > m:
            top_10_items.append(rand)
            top_10_items.remove(m)

    print(top_10_items)

    cnt+=1
    if cnt==20:
        break

Answer 8

//finding the bigest number in the array//

double big = x[0];
for(t=0;t<x[t];t++)
{
    if(x[t]>big)
    {
        big=x[t];
    }
}
printf("\nThe bigest number is    %0.2lf  \n",big);