Q:

What structure is used for accessing the most frequent elements top k over a stream of elements?

Let's say you want the top k elements. Then given the array, there is an O(n) O(n) space approach. But what if you have a stream of elements, this means that each time you'd append an element to the end of your list, you'd have to do this O(n) time O(n) space approach. Let's say your elements are distinct elements of a set. You can maintain a frequency map, but you'd still have to do the O(n) approach to find the top k elements. Is this is what is done in production? What data structure is used to efficiently keep top k elements with updated frequencies? 

A:

This is possible in $\mathcal O(\log n)$ time using self-balancing tree (or heap), using frequencies as keys. This extends the node to keep a list (or once more a tree) of elements of equal frequency.
To access top k elements you can either augment the tree with additional pointers to allow traversal in $k$ steps or use $\mathcal O(\log n)$ recursive one.
Better approach is to keep $k$ elements in that tree-like structure and in another one the rest.
If elements are fixed, you can use hash-table to store them, so keeping a table per frequency would result in expected time $\mathcal O(1)$, here using knowledge of the elements will help to minimize number of collisions.

