Filtered-Space Saving Top-K

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.

Weighted Random: algorithms for sampling from discrete probability distributions

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