# Find largest $k$ numbers in Max Heap in $O(n\log k)$

I have a data stream with $$n$$ numbers and I want to find the largest $$k$$ of them ($$k \ll n$$). I want to use a priority queue with max heap of size $$k$$, so I will have space complexity $$O(k)$$, which is space efficient. The algorithm that I will use work with the following way:

• Insert the first $$k$$ elements to the priority queue
• Find their minimum
• While there is more data in the stream:
• If the new element is larger than the current minimum, replace the current minimum with the new element, and find the new current minimum

I have found in various posts that with this way I can have time complexity $$O(n \log k)$$. But when I want to find the new minimum, I will need $$O(k)$$ in the worst case, and I am confused about what I can do.

• Use min heap instead of max heap. The extract_min and insertion time would be $O(\log k)$. Overall time would be $O(n \log k)$. – Inuyasha Yagami Jan 10 at 13:17