Timeline for Keep k+ties largest elements in a stream
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 6, 2015 at 8:56 | comment | added | D.W.♦ | @novadiva, What specifically is your uncertainty? Have you tried implementing it? What specifically are you unclear on? You might edit the question to show the pseudocode for the algorithm as you understand it, and try to frame a specific question about a specific aspect of the pseudocode that you're not clear on. | |
| Jan 6, 2015 at 14:38 | comment | added | novadiva | I'd like to get a better explanation of how I can implement it efficiently, though... | |
| Jan 6, 2015 at 11:57 | comment | added | D.W.♦ | @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. | |
| Jan 6, 2015 at 8:24 | comment | added | novadiva | 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). | |
| Jan 6, 2015 at 6:53 | comment | added | D.W.♦ | @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$). | |
| Jan 6, 2015 at 6:12 | comment | added | novadiva | 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. | |
| Jan 6, 2015 at 5:45 | history | answered | D.W.♦ | CC BY-SA 3.0 |