You are using a randomized algorithm to approximate the smallest element in a collection of (object, count) pairs. Instead, use a min-heap to find the smallest

You are using a randomized algorithm to approximate the smallest element in a collection of (object, count) pairs. Instead, use a min-heap to find the smallest element. You do need a hash table as well to keep track of items' locations in the heap. You don't have to do any pop operations - since you only need to remove something from the list when you have a new item with count = 1, you can just replace the item at the root of the heap. This is probably also not the simplest way to get a reasonable approximation. Certainly those Hayes algorithms are better. You could also try something like, read in 2N elements, sort them, and drop the least-frequent N of them. Then read in N more and repeat. Pretty hacky though. You could also try bloom filters.