Introduction to Top K Elements

About the pattern

The top k elements pattern is an important technique in coding that helps us efficiently find a specific number of elements, known as $k$, from a set of data. This is particularly useful when we’re tasked with identifying the largest, smallest, or most/least frequent elements within an unsorted collection.

To solve tasks like these, one might think to sort the entire collection first, which takes $O(n \log(n))$ time, and then select the top k elements, taking additional $O(k)$ time. However, the top k elements pattern bypasses the need for full sorting, reducing the time complexity to $O(n \log k)$ by managing which elements we compare and keep track of.

Which data structure can we use to solve such problems? A heap is the best data structure to keep track of the smallest or largest $k$ ...