Algorithm

Filtered-Space Saving (FSS) is a data structure and algorithm combination useful for accurately estimating the top k most frequent values appearing in a stream while using a constant, minimal memory footprint.

The optimal solution for weighted random should be the Alias Method. It requires $O\left(n\right)$ time to initialize, $O\left(1\right)$ time to make a selection, and $O\left(n\right)$ memory.