Identifying the top k elements pattern

Many problems where we need to find and process the top k items in a fixed-sized dataset or a stream (a sequence of items that arrives one at a time, where the total count may not be known in advance) can be solved using the top k technique. These are generally medium or hard problems where we are given a dataset and a function f (an aggregating function such as sum, average, min, or max, as introduced in the previous lesson) and we need to find the aggregated value of the function f over the top k items in the dataset. While there may be other ways to solve such problems, the technique using a k-sized heap is generally the most efficient.

If the problem statement or its solution follows the generic template below, it can be solved by applying the k-largest-items finding technique (the top k technique applied to find the k largest items).

Example