Loading...
Top-K, streaming medians, and merges where partial ordering beats full sorting.
4 questions in Data Structures & Algorithms.
Nothing about correctness - it works. It throws away the sortedness you were given and pays O of N log N to rebuild it, where merging costs O of N log k, and it requires every element resident at once where a merge requires k. On lists that arrive as streams the second objection is the one that disqualifies it outright.
Keep a min-heap holding exactly the K largest values seen. Its root is the answer, so the query is a read rather than a search, and every value smaller than that root is discarded the moment it arrives. What you give up is the ability to answer for any K larger than the one you chose, which is why the first thing to establish is whether K is fixed.
Split the values across a max-heap of the lower half and a min-heap of the upper half, so the median is read off one or both tops. Balancing by size alone is what breaks it: a new value has to enter through the heap it belongs to by value and be transferred across, never pushed into whichever heap is currently smaller.
Count occurrences, then push counts through a min-heap capped at size k, evicting the smallest whenever the heap overflows. That is O(n log k) rather than the O(n log n) of a full sort, it needs only k items resident at once, and it works on a stream you cannot re-read.