Heaps and priority queues

What it is

A heap is a tree-shaped structure that keeps the smallest (or largest) element accessible in O(1) and lets you insert or remove that extreme element in O(log n). It's the tool of choice whenever a problem needs "the current best/next/smallest" repeatedly, rather than a single sort at the end — a full sort costs O(n log n) up front and doesn't update well as new elements arrive, while a heap does both incrementally. Many heap problems actually run two heaps (a max-heap of smaller values and a min-heap of larger ones) or a heap paired with a hash map for tie-breaking or scheduling by count.

When it applies

• You need the k largest/smallest/closest elements out of a stream or a large collection, without fully sorting everything.
• You need the running median, running k-th largest, or any statistic that must be re-answered after every insertion.
• You're merging several already-sorted sequences and need "the next smallest across all of them" repeatedly — a heap of one candidate per sequence does this in log(number of sequences) per step.
• Scheduling problems where you always want to act on "whatever is most in-demand right now" (the most frequent remaining task, the room that frees up soonest).
• A one-time need for the k-th element, with no ongoing order to maintain, is better served by quickselect's average O(n) than by heap overhead; and if the values arrive already sorted or nearly so, a two-pointer merge may beat a heap outright.

Tells in the problem

• "k-th largest," "k closest," "top k frequent" — especially when the collection keeps growing (a stream, repeated add calls).
• "Running median" or any statistic re-queried after every new value.
• Merging k sorted lists or sequences into one sorted output.
• A cooldown or scarcity constraint where you should always schedule "whichever type has the most remaining" next (task scheduling, string reorganization so no two identical characters are adjacent).
• "Minimum interval/room that contains this point" queried many times — a heap ordered by end time or size answers each query without rescanning everything.

The classic mistake

Reaching for a heap when the count k is a large fraction of n (say k ~ n), where maintaining a heap of size k costs about as much as just sorting and slicing — the heap only pays off when k is small relative to n. The subtler version of this mistake is picking the wrong heap direction: to find the k largest elements out of a stream, you want a min-heap of size k (so the smallest of your current top-k is the one you can cheaply compare against and evict), not a max-heap of everything, which forces you to keep every element you've seen. Interviewers notice when a candidate reaches for the max-heap-of-everything version and doesn't catch that it defeats the point of using a heap at all.

Questions to start with

• Kth Largest Element in an Array — the base case: a fixed array, one query, where a size-k min-heap beats a full sort.
• K Closest Points to Origin — the same size-k-heap idea with a computed key (distance) instead of the raw value.
• Top K Frequent Elements — adds a counting step before the heap, and introduces bucket sort as the O(n) alternative worth mentioning.
• Kth Largest Element in a Stream — turns the static version into an online one: the heap persists across add calls instead of being rebuilt.
• Find Median from Data Stream — the two-heap technique, balancing a max-heap of the lower half against a min-heap of the upper half.
• Merge K Sorted Lists — a heap of one candidate per list, replacing an O(kn) pairwise merge with O(n log k).
• Task Scheduler — scheduling by "most remaining count," where the heap enforces the cooldown constraint step by step.