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
-
3Possible duplicate of max value in array CNotBad4U– NotBad4U2017-11-17 18:25:56 +00:00Commented Nov 17, 2017 at 18:25
-
This question is not a duplicate of that. The linked question is asking how to find the single largest value in an array. This one is asking how to get the X largest values in the array. Much different.Jim Mischel– Jim Mischel2017-11-18 04:12:53 +00:00Commented Nov 18, 2017 at 4:12
Add a comment
|
4 Answers
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 >.
Comments
- Sort the array and take the first
Xelements - Use your language's
maxfunction to find the largest element. Extract it from the array. RepeatXtimes.
Comments
You can make a min heap, and call the ExtractMin function (len(arr) - x) times to get Xth largest value.
Comments
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.
2 Comments
Jim Mischel
DomainFlag
He didn't specify what language he is using so a raw implementation will be handy for him so he can adopt it easily to his case, secondly to freshen my knowledge regarding sorting algorithms some time. :p