Find n largest elements from an array

Question

I have an array

A[4]={4,5,9,1}

I need it would give the first 3 top elements like 9,5,4

I know how to find the max element but how to find the 2nd and 3rd max?

i.e if

max=A[0]
for(i=1;i<4;i++)
{
  if (A[i]>max)
  {
    max=A[i];
    location=i+1;
  }
}

actually sorting will not be suitable for my application because,

the position number is also important for me i.e. I have to know in which positions the first 3 maximum is occurring, here it is in 0th,1th and 2nd position...so I am thinking of a logic

that after getting the max value if I could put 0 at that location and could apply the same steps for that new array i.e.{4,5,0,1}

But I am bit confused how to put my logic in code

Answer 1

Consider using the technique employed in the Python standard library. It uses an underlying heap data structure:

def nlargest(n, iterable):
    """Find the n largest elements in a dataset.

    Equivalent to:  sorted(iterable, reverse=True)[:n]
    """
    if n < 0:
        return []
    it = iter(iterable)
    result = list(islice(it, n))
    if not result:
        return result
    heapify(result)
    for elem in it:
        heappushpop(result, elem)
    result.sort(reverse=True)
    return result

The steps are:

1. Make an n length fixed array to hold the results.
2. Populate the array with the first n elements of the input.
3. Transform the array into a minheap.
4. Loop over remaining inputs, replacing the top element of the heap if new data element is larger.
5. If needed, sort the final n elements.

The heap approach is memory efficient (not requiring more memory than the target output) and typically has a very low number of comparisons (see this comparative analysis).