1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

Keep a binary heap, where each element in the heap is a unique key value together with a pointer to a list of all the items with that key value.

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – novadiva Jan 6 '15 at 6:12
  • $\begingroup$ @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$). $\endgroup$ – D.W. Jan 6 '15 at 6:53
  • $\begingroup$ 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). $\endgroup$ – novadiva Jan 6 '15 at 8:24
  • $\begingroup$ @SergeyIvanov, there is no problem if your min-heap has more elements than you're supposed to have (counting multiplicity). It doesn't cause any problems. At the end when you want to produce output, you can deal with it easily, but at each step along the way, you can ignore it. $\endgroup$ – D.W. Jan 6 '15 at 11:57
  • $\begingroup$ I'd like to get a better explanation of how I can implement it efficiently, though... $\endgroup$ – novadiva Jan 6 '15 at 14:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.