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.