CODEWITHSUNDEEP
algorithm
user8959288
user8959288

Reputation:

How to get X largest values from array

I have array: [2 , 4 , 5, 1 , 4 , 20]

How to get X highest values from this array?

Like this:

getHighest(2): 25, 5
getHighest(3): 25, 5, 4

Upvotes: 0

Views: 2073

Answers (4)

Jim Mischel
Jim Mischel

Reputation: 133975

The basic idea is to create a priority queue (max heap) of the first X items. Then, for each remaining item in the array, if it's smaller than the first item on the heap, remove the first item from the heap and add the new item. Something like this:

heap = new maxHeap();
for (i = 0; i < X; i++)
{
    heap.Add(a[i]);
}
for (; i < a.Length; ++i)
{
    if (a[i] < heap.peek())
    {
        heap.removeFirst();
        heap.Add(a[i]);
    }
}
// at this point, the smallest X items are on the heap.
// Remove them:
while (!heap.IsEmpty())
{
    print(heap.removeFirst());
}

Note that what I describe above is how to get the X smallest items from the array. If you want the X largest, create a min heap and change the comparison from < to >.

Upvotes: 3

DomainFlag
DomainFlag

Reputation: 564

A naive C++ implementation is sorting the array descending by Quick Sort algorithm as in this example below:

void swapArray(int * tab, int ind1, int ind2) {
    int swap = tab[ind1];
    tab[ind1] = tab[ind2];
    tab[ind2] = swap;
}

int sortArray(int * tab, int min, int max) {
    int pivot = max;
    bool leftSwapping = true;
    while(min < max) {
        if(leftSwapping) {
            if(tab[min] < tab[pivot]) {
                swapArray(tab, min, pivot);
                pivot = min;
                max--;
                leftSwapping = false;
            } else {
                min++;
            }
        } else {
            if(tab[max] > tab[pivot]) {
                swapArray(tab, max, pivot);
                pivot = max;
                min++;
                leftSwapping = true;
            } else {
                max--;
            }
        }
    }
    return pivot;
}

void quickSort(int * tab, int min, int max) {
    if(min < max) {
        int pivot = sortArray(tab, min, max);

        quickSort(tab, min, pivot-1);
        quickSort(tab, pivot+1, max);
    }
};

And you can loop as many values you need out of array. Note: that QuickSort is not a stable algorithm, so Merge Sort and Insertion Sort can be handy in this case depending on you cause. This is in the case that you want to use multiple times the getHighest function, if not just use the simple selection sort and take as many values as you want.

Upvotes: 0

harshil9968
harshil9968

Reputation: 3244

You can make a min heap, and call the ExtractMin function (len(arr) - x) times to get Xth largest value.

Upvotes: 1

Prune
Prune

Reputation: 77827

  1. Sort the array and take the first X elements
  2. Use your language's max function to find the largest element. Extract it from the array. Repeat X times.

Upvotes: 2

Related Questions