Would it be quicker to use a binary heap to get the top x amount of integers from an array or use quick sort

Question

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[];

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.

Thanks

Answer 1

Let's take an example for both these cases:-

Method 1 (Use Max Heap) :-

1) Build a Max Heap tree in O(n)
2) Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)

Time complexity: O(n + klogn)

Method 2 (Use quick sort):-

1) Sort the elements in descending order in O(nLogn)
2) Print the first k numbers of the sorted array O(k).

Time complexity: O(nlogn)