To get the highest X amount of integers from an array, do you guys think that using a binary heap like this would be quicker:
binary heap to get the highest integer
store the highest integer
remove the highest integer from the array
repeat until we have the highest X amount from the array
Or would it be faster to just use quick sort and take the top x amount of integers from the array?.
EDIT: I should also add that the array can't stay sorted as it has several variables that we want to sort by, e.g:
class cl{
int var;
int var1;
int var2;
};
cl clArr[100];
So, we can request to get the highest integers from any of the variables.
Writing it down, it seems like a quick sort may be a better idea, although I'd like some opinions please, mostly what would be the fastest option.
It actually does.
It states that nth_element has average linear complexivity.
Using heap you have linear complexivity of making heap and x*log(n) for extracting values. Depending on relative sizes of n and x total complexivity is somewhere between linear and n*log(n).
So nth_element is expected to be faster and easier to use in this case.
Sorting has O(n*log(n)), so sorting whole sequence is counter-productive.