We have an array A of size n, which contains random positive integers of any size, i.e. not sorted.

What algorithm can find the k largest positive integers in O(n log k) time? Where k is k <= n/2.

I can see a bottom-up heap, which can be constructed in O(n) time, then each removeMax() from the heap would take O(log n) time, and when this is iterated k times it gives: O(k log n).
How do you obtain O(n log k) though? I smell that this has something to do with using one of the well-known sorting algorithms, Quicksort? Mergesort? Heapsort? But which one, and how do you justify that you get O(n log k)?

All of these best sorting algorithms can sort the entire array in O(n log n) time (well, except Quicksort, if you want to be completely formal). But which one can sort k of them in O(n log k) time?