1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How does the heap approach update frequency? Let's say you have heap with priority by frequency, that means each element (seen so far) can only lie within 1 index (and within index's subtree), so if you update an element's frequency you would need to find that element, pull it out of that index, and insert it into frequency + 1 node. $\endgroup$ – Jeremy Fisher Apr 17 '18 at 22:49
  • $\begingroup$ Yes. There are two ways, either exactly as you wrote, which is still logarithmic or another approach keep self balanced tree with top k frequencies, which extends node into another tree of elements of same frequency (to avoid linear search anywhere) and update position in the tree. When element from outside the main-k-top tree is eligible to advance from rest-elements tree it will be merged with existing node (otherwise it was not eligible). Another situation is when some elements from existing node gets +1 and creates new node. In that case the min of the tree is pushed out. $\endgroup$ – Evil Apr 17 '18 at 23:48

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.