Optimal algorithm to return largest k elements from an array of infinite number of elements in running stream

Question

I have a running stream of integers, how can I take largest k elements from this stream at any point of time.

Answer 1

Easiest solution would be to populate a min-heap of size k.

First, populate the heap with the first k elements.

Next, for each element in the stream - check if it is larger than the heap's head, and if it is - pop the current head, and insert the new element instead.

At any point during the stream - the heap contains the largest k elements.

This algorithm is O(nlogk), where n is the number of elements encountered so far in the stream.

---

Another solution, a bit more complex but theoretically better in terms of asymptotic complexity in some cases, is to hold an array of 2k elements.

First, load the first 2k elements.
Run Selection Algorithm, and find the highest k out of them. Discard the rest, at this point you have only k elements left in the array.
Now, fill the array again with the next k elements, and repeat.

At each point, the array contains the k largest elements, and up to k more elements that are not the largest. You can run Selection Algorithm for each query on this array.

Run time analysis:

Maintaining the array: Each selection algorithm is O(2k) = O(k). This is done once every k elements, so n/k times if n indicates the number of elements seen so far, which gives us O(n/k * 2k) = O(n).

In addition, each query is O(k), if the number of queries is Q, this gives us O(n + Q*k) run-time.

In order to this solution to be more efficient, we need Q*k < nlogk

Q*k < nlogk
Q < n/k * logk

So, if number of queries is limited as suggested above, this solution could be more efficient in terms of asymptotic complexity.

---

In practice, getting top k is usually done by using the min-heap solution, at least where I've seen the need of it.