Common Heaps Pattern

Recognizing a heap as the right data structure is only the first step. The next is knowing which pattern to apply. This lesson covers the two most important heap patterns in coding interviews: the Top-K pattern and the K-way merge pattern. They represent two fundamentally different uses of a heap, and together they cover the majority of heap-based interview problems.

Top-K pattern

The Top-K pattern uses a heap of fixed size $k$ to efficiently find the K largest or K smallest elements from a collection without sorting the entire dataset. For the K largest elements, we maintain a min-heap of size K. As we scan through the data, we push each element onto the heap. When the heap exceeds size K, we pop the smallest element. By the end of the scan, the heap contains exactly the K largest elements. The smallest among them, at the root, is the Kth largest overall.

For the K smallest elements, we maintain a max-heap of size K and pop whenever the heap exceeds K, discarding the largest seen so far. The key insight is that we never need to sort the full dataset. We only maintain a small heap of size K throughout the traversal.

Sorting the entire input and slicing the last K elements gives the right answer, but costs $O(n log n)$. A heap-based approach costs $O(n log k)$, which is significantly faster when K is much smaller than n. In an interview, sorting the full dataset to find K elements signals that we missed the heap optimization entirely.

When to reach for it

The signal is any problem that asks for K elements from a larger collection without requiring the full collection to be sorted. The collection may be static or arrive as a stream. If the problem involves finding the Kth largest or smallest element, or returning the top K elements by some criteria, this is the pattern.

Time and space complexity

• Time $O(n$ ...