LC Patterns — Heap / Priority Queue

The Python toolbox (interviews are heapq interviews)

import heapq
h = []
heapq.heappush(h, x)        # O(log n)
x = heapq.heappop(h)        # O(log n), pops MIN
h[0]                        # O(1) peek min
heapq.heapify(lst)          # O(n) — NOT n log n; say this, it gets asked
heapq.heappushpop(h, x)     # push then pop — faster than push;pop, keeps size
heapq.nlargest(k, iterable, key=...)   # fine for one-shot top-k

The five facts interviewers probe

1. heapify is O(n). Sift-down from the last parent; the sum Σ (nodes at height h) · h telescopes to O(n). Building by n pushes is O(n log n) — the distinction matters.
2. Python has only a min-heap. Max-heap = push negated values (-x), or negate the key in a tuple. Negate on the way in AND out — the classic silent bug.
3. Tuples break ties. (priority, tiebreak, payload) — if payloads aren't comparable (e.g. ListNodes in LC 23), you must insert a unique counter as the tiebreak: (val, i, node). Otherwise it crashes at runtime; know it before it bites mid-interview.
4. No decrease-key, no arbitrary delete. The standard workaround is lazy deletion: push the updated entry, and when popping, discard entries that are stale (check against a live dict/set). This idea powers Pattern 10 (Dijkstra) and Pattern 11 (design problems).
5. A size-k heap flips polarity. To keep the k largest, use a min-heap of size k (the root is the weakest member — the gatekeeper; anything beating it gets in, and the old root leaves). To keep the k smallest, use a max-heap of size k. Rehearse: "min-heap for the top-k largest — the root is the bar to clear." Getting this backwards is the #1 heap interview error.

Universal pitfalls

1. Heap when a sort would do (input static, all elements needed) — costs you the "knows their tools" signal. State why a heap: the set changes while I query.
2. O(n log n) when O(n log k) was the point. Top-k with a full heap of n elements works but misses the whole reason the question was asked. Keep the heap at size k.
3. Forgetting the heap can hold stale/expired entries — in time-based problems, always pop-while-invalid before reading h[0].
4. Comparator direction under negation — after negating for a max-heap, secondary tiebreaks may need negating too (or not!). Work one concrete example by hand.
5. Mutating priorities of items already in the heap (e.g. counts in a frequency heap) — the heap doesn't reorder itself. Re-push instead (lazy deletion), or restructure the loop so priorities are fixed at push time.

What it is: From n items, return the k largest / smallest / closest / most frequent — with k usually much smaller than n. Stream all n items through a heap capped at size k: the heap always holds the current best k, and its root is the weakest of them, deciding admission for each new item.

Intuition: you don't need any order among the n−k losers — so don't pay to sort them. A size-k min-heap (for the top-k largest) keeps the invariant "the heap is the best k seen so far" at O(log k) per element → O(n log k) total, O(k) space, and it works on streams too big to hold in memory (say this — it's the systems-flavored win).

Approach: iterate; if len(h) < k push; else if x > h[0] do heappushpop(h, x). For "k closest points," the key is distance (no sqrt needed — it's monotonic); for "k most frequent," build a Counter first, then heap over (count, elem). Alternatives to name: quickselect (O(n) avg, offline only), bucket sort by count (O(n) for frequencies, since counts ≤ n — the follow-up for LC 347).

What it is: Same top-k idea, but as a design problem: a class receives values one at a time (add(val)) and must answer "the current k-th largest" after every insertion, forever. The size-k heap is the object's persistent state.

Intuition: Pattern 1's loop invariant — "the heap holds the best k so far" — becomes a class invariant that survives across calls. The root of the size-k min-heap is the k-th largest at all times, so queries are O(1) and adds are O(log k). This is the purest demonstration that heaps are for changing sets: an offline sort is impossible because the data never stops arriving.

Approach: constructor: heapify the seed list, pop down to size k. add: push, and if the size exceeds k, pop; return h[0]. Variants maintain a set of available resources instead of top-k: the smallest unused number, the cheapest free seat — same skeleton, the heap holds "currently available" and you pop the best.

What it is: Maintain a stream's median (or any fixed percentile) as numbers arrive. Split the numbers into a lower half and an upper half — a max-heap for the small half, a min-heap for the large half — so both inner boundaries of the split are peekable in O(1), and the median sits on them.

Intuition: the median only ever needs two values: the largest of the small half and the smallest of the large half. Two heaps expose exactly those two, facing each other. Keep the sizes balanced (equal, or the lower half one bigger) and the median is lo[0] or (lo[0]+hi[0])/2. Re-sorting per query would be O(n log n) each insert; two heaps make it O(log n) insert, O(1) query.

Approach: the safe insertion dance (memorize it — ad-hoc balancing breeds bugs): always push onto the max-heap first, then move its top to the min-heap, then if the min-heap is bigger, move one back. Three lines, provably keeps both invariants (ordering between halves + size balance) with no case analysis. Sliding-window median adds removal: use lazy deletion with a counter of "dead" elements per side and rebalance on logical sizes.

What it is: k already-sorted sequences (lists, arrays, matrix rows, or implicit sequences like "pairs using element i") must be merged, or their combined k-th smallest found. The heap holds one candidate per sequence — each sequence's current head — and popping the global min tells you which sequence advances.

Intuition: at any moment, the next element of the merged output must be one of the k current heads — so keep exactly those k heads in a min-heap. Pop the winner, push its successor from the same sequence: O(total log k). The powerful generalization: the "sequences" can be implicit — in LC 373, row i is the sequence (nums1[i]+nums2[0]), (nums1[i]+nums2[1]), …, never materialized; you only need a rule for "successor of this element." And it's lazy: for "k-th smallest of a huge implicit space" you pop only k times and never touch the rest — the heap explores a sorted implicit space frontier-first.

Approach: seed the heap with each list's head as (val, list_idx, node/ptr) — the unique index is the tiebreak (§0 fact 3). Loop: pop, append to output (or count toward k), push the successor if it exists. For implicit spaces, guard against pushing the same cell twice (a visited set, or a seeding discipline). LC 632 is this skeleton + tracking the running max across heads: range = (heap min, current max).

What it is: A process is literally defined as "repeatedly take the largest (or two largest), do something to them, maybe put a result back" — smashing stones, halving numbers, combining piles. The heap isn't an optimization; it's the direct implementation of the problem statement.

Intuition: the problem is the heap's API read aloud. When the next action always applies to the current extreme, and actions create new elements that re-enter the pool, no static ordering can work — sorted order is invalidated by every reinsertion. Heapify once (O(n) — §0 fact 1), then each step is O(log n).

Approach: heapify the input (negate for a max-heap), loop while the termination condition (heap size > 1, target not reached, …): pop what you need, compute, push the result back. Termination usually needs a one-line argument — e.g. "each op strictly decreases the total, so it ends." Say it; it's cheap rigor that reads as seniority.

What it is: Rebuild a string/sequence from character counts under an adjacency rule — no two equal letters next to each other, or at least k apart. Always place the most abundant remaining item that is currently allowed, so no single item's surplus gets stranded at the end.

Intuition: the danger is one letter outnumbering everything else — so spend the majority letter as fast as legally possible, i.e. greedily by remaining count. Counts change after every placement, so you need "current max count, dynamically" = a max-heap over (count, char). A cooldown queue holds just-used letters until they're legal again, then returns them to the heap. Feasibility check first: impossible when max_count > (n + 1) // 2 (for the no-adjacent case).

Approach: Counter → max-heap of (-count, char). Loop: pop the best legal letter, emit it, decrement, park it in a small cooling area (the previous letter, or a queue of the last k−1), and release cooled letters back into the heap. Simple no-adjacent alternative: fill even indices first with the majority letter, then odd — O(n), no heap; offer it as the follow-up.

What it is: Tasks/jobs/meetings arrive at given times and must run on workers/CPUs/rooms according to tie-break rules ("shortest job first among those available", "lowest-numbered free room"). You simulate the timeline, and heaps hold what's ready and what's busy.

Intuition: two clocks are running: arrival order (sort by arrival time once) and service order (priority among currently-available tasks — a heap, because availability changes as time advances). The canonical shape is two heaps: one keyed by "when it becomes free/available" (future events), one keyed by priority (ready now) — and you shuttle items from the first to the second as the clock advances. The move everyone fumbles: when nothing is ready, jump time forward to the next event instead of incrementing by 1.

Approach: sort tasks by arrival (keep the original index for output/tie-breaks). Maintain busy = [(free_time, resource)] and ready = [(priority, tiebreak, task)]. Loop: if ready is empty, advance the clock to the next arrival; move arrived tasks into ready, release resources from busy whose free_time <= clock; pop ready, assign, push into busy with its completion time.

What it is: Given intervals (meetings, requests, buildings), answer "how many overlap at once" (min rooms) or "what's the max height profile" (skyline). Sort by start; sweep left→right; a min-heap of end times holds the intervals currently open — its size is the current concurrency, its root is the next one to expire.

Intuition: when a new interval starts, the only question is "has the earliest-ending open interval already finished?" — exactly the heap root. If h[0] <= start, that room is reusable (pop, reuse); otherwise concurrency grows. The max heap size over the sweep = the answer for rooms. The skyline is the max-heap sibling: the heap holds active building heights, and the visible height at any x is the heap max — with lazy deletion for buildings that ended.

Approach: rooms: sort by start; for each interval, if h and h[0] <= start: heappop(h); heappush(h, end); the answer is the max size. Skyline: events sorted by x (starts before ends at equal x — the tie rules are the problem), a max-heap of (height, end) with lazy pops; output a point whenever the visible max changes.

What it is: You make greedy choices as you scan, but keep every choice in a heap so that when you hit a wall (fuel runs out, deadline exceeded, budget blown), you can retroactively undo the worst past choice (or upgrade to the best skipped option) and continue. The heap stores the past, not the future.

Intuition: pure greedy fails because you can't know now which early sacrifice will hurt later — so don't decide now. Take the cheap default (walk past the station, take every course, use a ladder), record the alternative in a heap, and only when forced, cash in the single best correction: "which previous decision, if flipped, helps most?" That's one heap pop. This turns an exponential lookahead into O(n log n), and the proof is a clean exchange argument.

Approach: three canonical forms — memorize the mapping:

• 871 (refueling): drive past stations, push their fuel amounts into a max-heap; when the tank goes negative, pop the largest skipped fuel (repeat if needed); count pops. Unreachable if the heap empties while still negative.
• 630 (courses): sort by deadline; take every course, pushing its duration into a max-heap; when total time exceeds the current deadline, evict the longest course taken so far (pop) — you keep the count minus one but the maximum slack.
• 1642 (ladders+bricks): use a ladder on every climb, pushing climb sizes into a min-heap of size = ladders; when a new climb arrives and the heap is full, the smallest recorded climb gets downgraded to bricks (pop-push); stop when bricks go negative.

What it is: Shortest/cheapest/safest path where edges have weights (or cells have costs): the heap holds the frontier of partially-explored states keyed by current best cost, and popping finalizes states in globally optimal order. Covered in depth in graphs — this entry is the heap-side view.

Intuition: BFS finalizes nodes in distance order because every edge costs 1 — a plain queue suffices. With weights, "the next closest state" is no longer the queue front; it's a changing-set minimum → heap. The greedy invariant: when a state pops with cost c, no cheaper route to it can ever appear (all future pops cost ≥ c). Everything else — grid variants, "minimize the max edge on the path" — is the same invariant with a different cost formula.

Approach: a dist map, a heap of (cost, state) seeded with the source. Pop; if stale (cost > dist[state]) skip — this lazy-deletion guard is Python's replacement for decrease-key (§0 fact 4); relax neighbors, pushing improved costs. For min-max path problems the relaxation is new = max(cost_so_far, edge) instead of +.

What it is: Design-a-data-structure problems that need both extreme queries and arbitrary updates/removals — things a heap doesn't natively support. The trick: never physically delete or update in place. Keep the ground truth in a dict; push duplicates into the heap on every change; purge stale roots at query time.

Intuition: a heap can't find an arbitrary element, but it doesn't need to — wrongness is only visible at the top. So let garbage pile up inside, and validate only the root against the ground-truth map when someone peeks: while h and is_stale(h[0]): heappop(h). The amortized cost stays O(log N) over all pushed entries because each entry is popped at most once. This is Dijkstra's stale-pop guard (Pattern 10) promoted to a design principle.

Approach: two structures in tandem — truth: dict (the current value/location per key) and h: heap of (key-of-interest, version-or-value, id) snapshots. Mutations: update truth, push the new snapshot, never touch old entries. Queries: purge-then-peek. The staleness test = "does this heap entry still match truth?" — design that predicate first, the rest is boilerplate.