# Keep k+ties largest elements in a stream

I have $n$ numbers that come one by one, and when the last element comes, I want to output $k$ largest elements and those that are ties with the minimal element from this top-$k$ element.

For example, I have $[10, 7, 7, 9, 10, 10]$ and $k = 4$, then I want to output $[10, 9, 10, 10]$. However, if $[10, 7, 7, 9, 10]$ and $k = 4$ I want to output $[10, 7 , 7, 9, 10]$. Note that in the first example number of unique elements is less than $k$.

If I didn't want these ties, I'd probably use min-heap and keep track of top-$k$ elements in that heap, replacing minimum every time larger element comes from the stream. However, with ties I would have to perform searching inside the heap the element if it's already there and only then perform replacement/addition.

What is the best way to keep track of top-k + ties elements from the coming array of integers?

Note: $n>>k$.

For instance, with the input list $[10,5,7,5,7,9,10]$, the unique key values are $5,7,9,10$, so you'd have a heap containing the following 4 elements: $5$ (with a pointer to the list $[5]$), $7$ (with a pointer to the list $[7,7]$), $9$ (with a pointer to the list $[9]$), and $10$ (with a pointer to the list $[10,10]$). Now you can find the top-$k$ elements (with ties) straightforwardly using this heap data structure.
• I edited my post. Please, see examples one more time. Do you recommend to use heap of size $n$ (in general case) or of fixed size (e.g. $k$)? If the latter, how do you perform insertion/deletion of a new element? The point is that an incoming element can be greater than min-element of the heap and will reduce the total number of "unique" elements not by 1, but by the number of minimum elements in the heap at the moment. – novadiva Jan 6 '15 at 6:12
• @SergeyIvanov, either is fine. A min-heap of size $k$ or size $n$ will both work. Insertion/deletion is via the standard algorithm. I propose to keep track of the $k$ smallest unique key values, and the multiplicity of each. This is sufficient to answer your problem in all cases, including the two cases in your edited question (just start taking the smallest key values, from smallest to largest, counting the total number of items you've output, until you get to $k$). – D.W. Jan 6 '15 at 6:53
• As I said $k << n$ (usually k = 100, n = 1M), so there is a big overhead if you use a heap of size $n$. Then, if we keep a heap of size k, then we need to keep track of total amount of elements somehow. Imagine, $k = 4$ and you have [[1,1,1,1],[5,5],[6]] (totalling 7 elements). Now $3$ comes in and you have to remove all ones, so the resulting heap will be [[3],[5,5],[6]] (totalling 4 elements). The question is how do we insert/delete so that we do not end up with more elements than we are allowed to have (which is at least k). – novadiva Jan 6 '15 at 8:24