Heaps: The Interview Perspective

Heaps solve a specific and recurring interview problem: they provide repeated access to the smallest or largest element in a collection, even as that collection changes.

Sorting works well when the data is fixed. We sort once, then process elements in order. But if new elements keep being added or existing ones are removed, maintaining sorted order becomes expensive because we may need to reorder the collection repeatedly.

A heap is designed for this exact scenario. It keeps the smallest or largest element at the top, allowing quick access in $O(1)$ time and efficient insertion or removal in $O (\log n)$ time, which is exactly what problems involving dynamic data require.

Why interviewers reach for heaps

A heap problem is almost always a problem about priority. When the solution requires repeatedly finding the minimum or maximum from a set that changes over time, sorting is too rigid, and a linear scan is too slow. A heap sits between the two: it maintains a partial ordering that is just strong enough to give us the extreme element in O(1) and update in ...