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.

  • 2
    $\begingroup$ 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)$. $\endgroup$ Jan 10 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.