Advanced Heap Techniques

Trees & HeapsPriority 4 of 5 — High value — a gap here costs you roundsHigh value Updated Nov 12, 2026
Section priorityPriority 5 of 5 — Must know — expect it in almost every loopMust knowPriority 4 of 5 — High value — a gap here costs you roundsHigh valuePriority 3 of 5 — Worth knowing — usually a variant of a must-know patternWorth knowingPriority 2 of 5 — Niche — read once, revisit only if a company is known to askNicheMarked on the sections that carry it — unmarked sections are background/reference.

Scope — The heap patterns a first pass should skip: lazy deletion, sweep-line “alive” heaps, regret greedy, resource-pool allocators, grid best-first search, and the structures beyond a plain binary heap; the six must-know templates stay in the parent sheet. See also — parent sheet: heap.md — the canonical top-k / k-way-merge / two-heap / interval-scheduling templates and the pattern-selection guide. Siblings split out of the same file: heap_examples.md — the worked LC solution archive; heap_language_apis.md — heapq / PriorityQueue API reference. Neighbouring sheets: Dijkstra.md — the PQ shortest-path algorithm these grid searches specialise; monotonic_queue.md — when a deque beats a lazy heap; streaming_algorithms.md — top-k over an unbounded stream.

LeetCode Problem Lists

Overview

Every technique here exists because a binary heap is missing an operation: it has no decrease-key, no remove-arbitrary, and no way to revise a past decision. Each pattern below is a different way of working around that with pushes and top-of-heap pops only.

Key Properties

  • Complexity: stated per template; all are O(n log n) or O(n log k) with amortised pops
  • Core Idea: never search the heap — push a new entry and clean only the top, only at read time
  • When to Use: after the heap.md templates are automatic; these are the tier-4 patterns that separate a “heap problem” from a “hard heap problem”

Problem Categories

Pattern Signature in the problem statement Anchor problems
Lazy deletion a pushed value later changes or is removed LC 3092, 2349, 480, 1825
Two mirrored lazy heaps max and min over the same map of corrections LC 2034
Sweep + alive heap “at every x, the max/min over all intervals covering x” LC 218, 1851
Bounded regret heap k free passes + a budget for everything else LC 1642, 1792
Greedy with regret you only learn you overcommitted later LC 871, 630, 502
Resource pools allocate the smallest free id, release at a known time LC 1942, 1606, 1801, 2073, 2102
Sort + fixed-size heap objective = sum(A) × max/min(B) LC 857, 1383
Grid best-first expand the cheapest cell, not the nearest LC 407, 778, 1631, 1368, 675
Range-jump grid DP each cell jumps to a range of cells LC 2617
Frequency uniqueness make all frequencies distinct with min deletions LC 1647, 1481
K-way merge variants merge virtual or nested sorted sources LC 632, 1439

Prerequisites

Each technique below extends one card in heap.md; have that card down first.

  • heap § Template 1: the size-k heap. The bounded regret heap (§ 3) and sort + fixed-size heap (§ 6) are this heap run inside a greedy.
  • heap § Template 2: count, then heap on the count. Lazy deletion (§ 1) is what it becomes when a count changes after it was pushed; frequency uniqueness (§ 9) is a case of it.
  • heap § Template 3: k-way merge. § 11’s variants change only the bookkeeping around the frontier.
  • heap § Template 5: an entry that expires by index and is popped only at the top. Lazy deletion (§ 1, § 12), the alive heap (§ 2) and the range-jump grid (§ 8) generalise that staleness test.
  • heap § Template 6: a min-heap of end times. The resource pools (§ 5) add a second heap for the free ids; the alive heap (§ 2) orders by value and expires by end.
  • Dijkstra.md: the PQ shortest path that grid best-first search (§ 7) runs on an implicit grid.

Recognition

Reach for this sheet only when the core template’s loop is not enough on its own: a pushed value changes, a decision must be revised, or the heap needs a second key.

Signal in the statement Constraint cue Reach for Not this if
a value already in the heap later changes or is removed 10⁵ mixed updates and queries § 1 Lazy deletion the value only ever grows and you read the max once at the end → a plain count
“max and min” over one map whose values are overwritten 10⁵ calls, reads interleaved § 1 two mirrored lazy heaps sortedcontainers / TreeMap allowed and asked for → ordered multiset
“at every x, the tallest / shortest interval covering x” N ≤ 10⁴–10⁵ intervals § 2 Sweep + alive heap only the count covering x is asked → difference array / heap § Template 6
“k ladders / k free passes”, the rest paid from a budget N ≤ 10⁵ § 3 Bounded regret heap no budget, just the k largest → heap § Template 1
“minimum number of stops”, “maximum courses”, you learn you overcommitted later N ≤ 10⁴–10⁵ § 4 Greedy with regret every item fits its window independently → sort + plain greedy
“smallest free chair / server”, resources released at known times N ≤ 10⁵ events § 5 Resource pools only how many resources are needed → heap § Template 6
objective sum(A over the chosen k) × max/min(B) n ≤ 10⁵, k ≤ n § 6 Sort + fixed-size heap the objective has one attribute → heap § Template 1
grid, the next cell to expand is the lowest / cheapest, not the nearest m·n ≤ 10⁴–10⁵ § 7 Grid best-first unit steps → BFS
each cell jumps to a range of cells in its row / column m·n ≤ 10⁵ § 8 Range-jump grid jumps are to single neighbours → BFS

Templates & Algorithms

1) Lazy Deletion — Heap + HashMap of Truth Priority 5 of 5 — Must know — expect it in almost every loop

Core Idea

A binary heap supports push / pop-top in O(log n), but not “update this element” or “remove that arbitrary element” — finding it alone is O(n).

So when an element’s key changes, we don’t touch the old entry. Instead:

text
HEAP    = a bag of CANDIDATES   (some are stale / outdated)
HASHMAP = the SOURCE OF TRUTH   (current real value of each key)

An entry (value, key) is stale iff value != hashmap[key]. We never hunt for stale entries; we only clean the top, and only at read time:

python
# the whole pattern in 3 lines
c_map[key] = new_value                          # 1. update truth
heapq.heappush(pq, (-new_value, key))           # 2. push new candidate (old one stays!)
while pq and -pq[0][0] != c_map[pq[0][1]]:      # 3. pop stale tops until top is valid
    heapq.heappop(pq)

Pop only until the top is valid, then stop. Every other stale entry stays in the heap untouched — it may never be popped at all. Cleaning is lazy: pay only for the entries that actually block the answer.

text
pq (max-heap by count):  [5:A]  [4:B]  [3:A]  [2:C]  [1:B]  ...
                           ^stale (A is really 3 now)
                           |
           pop it ────────┘, now top = [4:B]
                                         ^ valid? -> STOP. Done.
                                           [3:A], [1:B] stay stale in the heap forever
                                           (or until they bubble to the top someday)

Why is this correct?

  • If the top is valid, it is the true max — every other entry in the heap is ≤ it, and no key’s true value can exceed its own most-recently-pushed entry (which is in the heap).
  • If the top is stale, its key’s true value is stored elsewhere in the heap (we pushed it on update), so discarding the stale copy loses nothing.

Why is this fast?

  • Each push creates at most one entry, and each entry is popped at most once over the entire run → total pops ≤ total pushes = O(n).
  • Amortized O(log n) per operation; heap size bounded by O(n).

Python template

python
# python
# IDEA: heap holds stale candidates; hashmap holds truth; clean top lazily
import heapq

class LazyMaxTracker:
    def __init__(self):
        self.truth = {}   # key -> current real value  (SOURCE OF TRUTH)
        self.pq = []      # max-heap of (-value, key)  (CANDIDATES, may be stale)

    def update(self, key, delta):
        # 1. update the truth
        self.truth[key] = self.truth.get(key, 0) + delta
        # 2. push new candidate -- do NOT remove the old entry
        heapq.heappush(self.pq, (-self.truth[key], key))

    def top(self):
        # 3. lazy delete: pop stale tops ONLY until the top is valid
        while self.pq and -self.pq[0][0] != self.truth[self.pq[0][1]]:
            heapq.heappop(self.pq)
        return -self.pq[0][0] if self.pq else 0

Java template

java
// java
// IDEA: PriorityQueue of stale candidates + HashMap of truth
class LazyMaxTracker {
    Map<Integer, Long> truth = new HashMap<>();               // key -> real value
    // max-heap by value: long[]{value, key}
    PriorityQueue<long[]> pq =
        new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));

    public void update(int key, long delta) {
        long v = truth.getOrDefault(key, 0L) + delta;
        truth.put(key, v);
        pq.offer(new long[]{v, key});                          // old entry left behind
    }

    public long top() {
        // pop stale tops only until the top is valid, then stop
        while (!pq.isEmpty() && pq.peek()[0] != truth.get((int) pq.peek()[1])) {
            pq.poll();
        }
        return pq.isEmpty() ? 0 : pq.peek()[0];
    }
}

Three flavors of “stale” — pick the invalidation test that fits the problem:

Flavor Stale test on pq[0] Typical problem
Value mismatch (hashmap of truth) -pq[0][0] != c_map[pq[0][1]] LC 3092 Most Frequent IDs
Deleted set / counter pq[0] in removed (then decrement) LC 480 Sliding Window Median, LC 1825 MK Average
Expired by time / index pq[0].end < day or pq[0].idx <= i - k LC 1353 Max Events, LC 239 Sliding Window Max

Gotchas

  • ⚠️ Clean at READ time by default. Cleaning after every push is safe whenever staleness is a pure function of the truth map — but it is wasted work when reads are rare, and it is not even defined for the expired-by-time flavour, where the query decides what has expired. When reads dominate it becomes a deliberate trade for O(1) reads; see the LC 2034 variant.
  • ⚠️ while, not if. Several stale entries can pile up on top of each other.
  • ⚠️ Guard pq non-empty inside the while condition and before reading pq[0] — the collection can legitimately become empty (LC 3092 example 2 → answer 0).
  • ⚠️ Don’t try to delete the old entry. That’s O(n) search and defeats the whole point.
  • ⚠️ Heap can grow to O(n) entries even if only a few distinct keys exist — that’s the space you trade for the speed.

Worked example — LC 3092 Most Frequent IDs

nums[i] is an ID and freq[i] adds (or, if negative, removes) that many copies of it; after each step, report the count of the most frequent ID, or 0 when the collection is empty. A plain heap fails because an ID’s count changes after it was pushed: when 2’s count drops from 3 to 0, the entry (-3, 2) is buried in the heap and cannot be reached in O(log n). The template above is the whole answer:

text
nums = [2,3,2,1],  freq = [3,2,-3,1]

step 0: c_map={2:3}          push(-3,2)   top=(-3,2) valid           -> ans 3
step 1: c_map={2:3,3:2}      push(-2,3)   top=(-3,2) valid           -> ans 3
step 2: c_map={2:0,3:2}      push( 0,2)   top=(-3,2) STALE (2 is 0)  -> pop
                                          top=(-2,3) valid -> STOP   -> ans 2
                                          ( (0,2) still sits in pq, untouched )
step 3: c_map={2:0,3:2,1:1}  push(-1,1)   top=(-2,3) valid           -> ans 2

output = [3,3,2,2]

Step 2 pops exactly one entry, the one blocking the answer, and leaves every other stale entry in place.

python
# python
# LC 3092 - Most Frequent IDs
# IDEA: hashmap of true counts + max-heap of (-count, id) candidates; pop stale tops at read time
# time = O(n log n), space = O(n)
import heapq

def mostFrequentIDs(nums, freq):
    c_map = {}   # id -> TRUE frequency
    pq = []      # max-heap of (-frequency, id), possibly stale
    ans = []
    for val, cnt in zip(nums, freq):
        c_map[val] = c_map.get(val, 0) + cnt         # 1. update the truth
        heapq.heappush(pq, (-c_map[val], val))       # 2. push; the old entry stays behind
        while pq and -pq[0][0] != c_map[pq[0][1]]:   # 3. pop stale tops only
            heapq.heappop(pq)
        ans.append(-pq[0][0] if pq else 0)           # 4. the top is now accurate
    return ans
java
// java
// LC 3092 - Most Frequent IDs
// IDEA: HashMap of true counts + max-heap of {count, id} candidates; poll stale tops at read time
// time = O(n log n), space = O(n)
public long[] mostFrequentIDs(int[] nums, int[] freq) {
    Map<Integer, Long> cMap = new HashMap<>();          // id -> TRUE frequency
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
    int n = nums.length;
    long[] ans = new long[n];
    for (int i = 0; i < n; i++) {
        int val = nums[i];
        long cur = cMap.getOrDefault(val, 0L) + freq[i];
        cMap.put(val, cur);                              // 1. update the truth
        pq.offer(new long[]{cur, val});                  // 2. the old entry stays behind
        while (!pq.isEmpty() && pq.peek()[0] != cMap.get((int) pq.peek()[1])) {
            pq.poll();                                   // 3. drop stale tops only
        }
        ans[i] = pq.isEmpty() ? 0 : pq.peek()[0];        // 4. read the answer
    }
    return ans;
}

Traps

  • The collection can become empty (nums=[5,5,3], freq=[2,-2,1] → [2,0,1]): when 5 hits 0 the pushed (0, 5) is valid (0 == c_map[5]) and the answer is correctly 0. Pushing zero counts is harmless and keeps the test uniform.
  • Counts reach n · max(freq) = 10¹⁰: use long in Java, or int overflows.

Similar problems — the same three steps

Problem LC # What goes stale Stale test
Design a Number Container System 2349 an index was reassigned a new number the index’s current number != this number
Stock Price Fluctuation 2034 a timestamp’s price was corrected, in two heaps price != price_map[ts]
Sliding Window Median 480 an element slid out of the window val in removed counter (§ 12)
Finding MK Average 1825 an element left the last-m stream delete-set / multiset
Maximum Number of Events 1353 an event’s deadline passed pq[0] < day
Minimum Number of Visited Cells in a Grid 2617 a cell can no longer reach the sweep per-row / per-column PQ (§ 8)
Dijkstra (743, 1631, 778) — a shorter path was found later d > dist[node]: continue

Dijkstra’s if d > dist[u]: continue line is a lazy delete: it discards a stale distance entry instead of doing a decrease-key on the heap.

Variant — two mirrored lazy heaps over one map (LC 2034) Priority 5 of 5 — Must know — expect it in almost every loop

What changes. The template above tracks one extreme of a map whose values accumulate. LC 2034 Stock Price Fluctuation breaks two of its preconditions at once:

Template 1 assumes LC 2034 gives you
one extreme is asked for maximum() and minimum() over the same map
the value accumulates — truth[k] += delta the value is overwritten — a later record corrects the price at a timestamp already seen
you may read the extreme rarely 10^5 mixed calls, reads and writes interleaved

The correction is what kills the naive heap: after update(1, 3) the entry (-10, 1) sitting in the max-heap is a price that never existed any more, and there is no way to reach it.

Core idea — one map of truth, two heaps mirroring it, and the same stale test in both:

text
price_map[ts] = price      <- SOURCE OF TRUTH (one per timestamp, overwritten on correction)
max_heap: (-price, ts)     <- CANDIDATES for maximum()
min_heap: ( price, ts)     <- CANDIDATES for minimum()

an entry is STALE  iff  its price != price_map[its ts]

current() needs no heap at all — track max_time as a running maximum and read the map, O(1).

Where to clean — this is the decision the problem actually turns on, and both answers are correct here:

clean at read time (maximum() / minimum()) clean at write time (end of update)
update O(log n) worst case O(log n) amortised
maximum / minimum O(log n) amortised O(1) worst case — the top is always valid
safe when always staleness is a pure function of the map
prefer when reads are rare, or a query defines “expired” reads dominate, or you want a flat read latency

Write-time cleaning is available here only because price_map is the sole thing that can make an entry stale, and only update touches it. With the expired-by-time flavour the query decides what has expired, so there is nothing to clean at write time.

Python

python
# python
# LC 2034 - Stock Price Fluctuation
# IDEA: one hashmap of truth + two mirrored lazy heaps; clean both tops inside update()
# time = update O(log n) amortised, current/maximum/minimum O(1), space = O(n)
import heapq

class StockPrice(object):
    def __init__(self):
        self.price_map = {}    # timestamp -> CURRENT price   (SOURCE OF TRUTH)
        self.max_time = 0      # biggest timestamp seen  -> current() is O(1)
        self.max_heap = []     # (-price, timestamp)     (CANDIDATES, may be stale)
        self.min_heap = []     # ( price, timestamp)

    def update(self, timestamp, price):
        # 1. overwrite the truth -- this is what makes old heap entries stale
        self.price_map[timestamp] = price
        self.max_time = max(self.max_time, timestamp)

        # 2. push into BOTH heaps; never remove the old entries
        heapq.heappush(self.max_heap, (-price, timestamp))
        heapq.heappush(self.min_heap, (price, timestamp))

        # 3. clean both tops: pop only while the top disagrees with price_map.
        #    No emptiness guard: the entry just pushed is valid, so neither heap can empty.
        while -self.max_heap[0][0] != self.price_map[self.max_heap[0][1]]:
            heapq.heappop(self.max_heap)
        while self.min_heap[0][0] != self.price_map[self.min_heap[0][1]]:
            heapq.heappop(self.min_heap)

    def current(self):
        return self.price_map[self.max_time]

    def maximum(self):
        return -self.max_heap[0][0]   # top is clean -> O(1)

    def minimum(self):
        return self.min_heap[0][0]

Move the two while loops into maximum() / minimum() and you have the read-time spelling — same heaps, same test, the amortisation moved to the other side. Then the while ... and ... non-empty guard is required, because a reader can be called before any clean.

Java

java
// java
// LC 2034 - Stock Price Fluctuation
// IDEA: HashMap of truth + two mirrored lazy heaps; both tops cleaned inside update()
// time = update O(log n) amortised, current/maximum/minimum O(1), space = O(n)
class StockPrice {
    private final Map<Integer, Integer> priceMap = new HashMap<>();   // ts -> CURRENT price
    private int maxTime = 0;
    // both heaps hold {price, timestamp}; only the ordering differs
    private final PriorityQueue<int[]> maxHeap =
        new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
    private final PriorityQueue<int[]> minHeap =
        new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

    public void update(int timestamp, int price) {
        priceMap.put(timestamp, price);
        maxTime = Math.max(maxTime, timestamp);
        maxHeap.offer(new int[]{price, timestamp});
        minHeap.offer(new int[]{price, timestamp});

        // clean BOTH tops; the entry just pushed is valid, so neither heap can empty
        while (maxHeap.peek()[0] != priceMap.get(maxHeap.peek()[1])) maxHeap.poll();
        while (minHeap.peek()[0] != priceMap.get(minHeap.peek()[1])) minHeap.poll();
    }

    public int current() { return priceMap.get(maxTime); }
    public int maximum() { return maxHeap.peek()[0]; }
    public int minimum() { return minHeap.peek()[0]; }
}

Trace — the official example, showing the one pop the correction costs:

text
update(1,10)  price_map={1:10}        max_heap=[(-10,1)]                 max=10  min=10
update(2, 5)  price_map={1:10, 2:5}   max_heap=[(-10,1),(-5,2)]          max=10  min=5
update(1, 3)  price_map={1:3,  2:5}   top (-10,1): price_map[1]=3 != 10  -> STALE, pop
                                      top  (-5,2): price_map[2]=5 == 5   -> valid, STOP
                                      max_heap=[(-5,2),(-3,1)]           max=5   min=3
update(4, 2)  price_map={1:3,2:5,4:2} max_heap=[(-5,2),(-3,1),(-2,4)]    max=5   min=2

min_heap still holds the stale (10,1) from step 1 — it is below (2,4),(3,1),(5,2),
so nothing ever asks about it. That is the point: it is never paid for.

Pitfalls

  • ⚠️ Don’t decide staleness by timestamp. (-10, 1) and (-3, 1) share a timestamp; only the price comparison against the map separates them.
  • ⚠️ current() is not maximum()'s neighbour. It is the price at the latest timestamp, not the latest price pushed — a correction to an old timestamp must not move it. Track max_time = max(max_time, timestamp) and never decrease it.
  • ⚠️ Two heaps, two cleans. A correction invalidates an entry in both mirrors; cleaning only the one you are about to read leaves the other wrong on its next call.
  • ⚠️ Pushing an unchanged price re-pushes a duplicate. Harmless — both copies are valid — but it is why the heaps are O(number of updates), not O(number of timestamps).

The alternative — an ordered multiset (TreeMap<price, count> / SortedList) deletes the old price on the spot, so no entry is ever stale and maximum() is exactly lastKey(). It costs a real O(log n) delete per update and a structure heapq does not have; see design_examples.md § Ordered Map. Two lazy heaps is the answer to give first — it is the one you can write in Python without sortedcontainers.

Similar problems — the mirrored / overwritten flavour

Problem LC # Truth map What a write invalidates
Stock Price Fluctuation 2034 timestamp -> price the old price of that timestamp, in both heaps
Design a Number Container System 2349 index -> number the old number at that index
Most Frequent IDs 3092 id -> frequency the previous frequency of that id
Maximum Frequency Stack 895 value -> count nothing — counts only rise, so no lazy delete is needed
Sliding Window Median 480 delete-counter an element that left the window
LRU / LFU Cache 146 / 460 key -> node why these use a linked list, not a heap: they need O(1), not O(log n)

Lazy deletion outside the heap — the same idea in other structures Priority 4 of 5 — High value — a gap here costs you rounds

Lazy deletion is not a heap trick. It is a general answer to one situation, and once you can name it you will see it in half the systems you use:

The structure’s invariant is expensive to restore, but cheap to test. So don’t restore it on write — mark, and test on read.

Every instance answers the same three questions:

  1. What marks a record dead? a tombstone, a counter, a newer version, or a mismatch with a separate source of truth.
  2. Who checks? the read path — always, and it must check before trusting what it found.
  3. Who reclaims the space? either the read that trips over it, or a background compaction.
Structure Deletion it cannot do cheaply What is left behind Validity test on read Who reclaims
Binary heap remove-arbitrary / decrease-key (O(n) to even find the element) the superseded (value, key) entry value != truth[key] the read that reaches the top
Open-addressing hash table delete — blanking a slot cuts every probe chain through it a tombstone slot, distinct from EMPTY probe skips tombstones, stops only at EMPTY rehash when the load factor counts tombstones in
BST / trie two-child delete (splice in the successor, rebalance) the node, with a deleted flag traversal ignores flagged nodes periodic rebuild when flagged > half
Dijkstra’s PQ decrease-key on an improved distance the old (dist, node) pair if d > dist[u]: continue the pop itself
LSM-tree (RocksDB, Cassandra, HBase) in-place delete — the SSTables are immutable a tombstone record with a newer timestamp newest version of the key wins on merge-read compaction
MVCC database (PostgreSQL) in-place update — concurrent readers still need the old row the old row version, stamped dead snapshot visibility check VACUUM
Redis key expiry scanning every key the instant its TTL lapses the expired key, still in the dict TTL checked when the key is touched that touch, plus a sampling cycle
Tracing GC knowing at x = null that nothing else points there the unreachable object reachability from the roots the GC cycle

So the if d > dist[u]: continue line in Dijkstra and the DELETED marker in a hash table are the same idea, and a Cassandra tombstone is that idea at disk scale. The vocabulary differs (“stale entry”, “tombstone”, “dead tuple”, “garbage”); the shape does not.

Two things it is often confused with

  • Lazy propagation in a segment tree defers work, not removal — a pending +v parked on a node, pushed down when a query descends. The deferred update is eventually applied to every descendant; a tombstone is applied to nothing, ever. Same adjective, opposite lifecycle. See segment_tree.md.
  • The monotonic deque (LC 239) is the eager counterpart: it pops dominated elements at write time, and it can, because domination is permanent — an element smaller than a newer one is useless forever. Reach for lazy deletion only when you cannot prove that; when you can, eager is strictly better (O(1) and no wasted space). See monotonic_queue.md.

What it costs you, stated honestly

  • Amortised, not worst case. Total pops ≤ total pushes, so the average is O(log n) — but one unlucky read can pop a long run of stale tops. If a latency bound is asked for rather than a throughput bound, say so, and offer the ordered multiset (or write-time cleaning, above).
  • Space is the currency. The container holds every version ever written until something reclaims it; this is exactly why a Cassandra table with a delete-heavy workload degrades until compaction runs, and why a tombstone-saturated hash table slows down before it is ever full.
  • Reads become non-trivial. The read path is now the only thing enforcing correctness, so a reader that forgets the check is a silent wrong answer, not a crash.

2) Sweep Line + Max Heap of “Alive” Intervals Priority 5 of 5 — Must know — expect it in almost every loop

Core Idea

The heap is used as a multiset of currently-alive values. We sweep a coordinate left→right; at each event we insert the value that just became alive, lazily evict values whose interval already ended, and read heap[0] = the current extreme among everything alive.

text
HEAP  = (value, endCoordinate)   sorted by value
ALIVE = heap entries with endCoordinate > sweepPosition

You never delete an interval when it ends — you delete it when it surfaces at the top and its end <= pos. This is the lazy-deletion idea from Template 8 with “expired by coordinate” as the staleness test.

Signature to recognize: “at every x, what is the max/min over all intervals covering x?”

Worked example — LC 218 The Skyline Problem

Each building [L, R, H] is alive on [L, R). The skyline changes exactly when the max alive height changes, so: sweep the sorted event x-coordinates, keep a max heap of (H, R), and emit a key point whenever the top height differs from the previously emitted height.

python
# python
# LC 218 - The Skyline Problem
# time = O(N log N), space = O(N)
# IDEA: sweep x; max-heap of (height, end); lazy-pop buildings whose end <= x; emit on height change
import heapq

class Solution(object):
    def getSkyline(self, buildings):
        # start event: (L, -H, R)   |   end event: (R, 0, 0)
        # sorting on (-H) puts starts before ends at the same x,
        # and taller starts before shorter starts
        events = [(L, -H, R) for L, R, H in buildings]
        events += list({(R, 0, 0) for _, R, _ in buildings})
        events.sort()

        res = [[0, 0]]                      # sentinel: ground level
        live = [(0, float('inf'))]          # max-heap of (-H, end); ground never expires

        for x, negH, R in events:
            # 1) LAZY EVICT: drop every alive entry that already ended
            while live[0][1] <= x:
                heapq.heappop(live)
            # 2) INSERT: only start events carry a height
            if negH:
                heapq.heappush(live, (negH, R))
            # 3) READ: top of heap = current skyline height
            if res[-1][1] != -live[0][0]:
                res.append([x, -live[0][0]])

        return res[1:]
java
// java
// LC 218 - The Skyline Problem
// time = O(N log N), space = O(N)
// IDEA: sweep x; max-heap of {height, end}; lazy-pop ended buildings; emit on height change
public List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2], b[1]});   // start: NEGATIVE height
        events.add(new int[]{b[1], 0, 0});          // end marker
    }
    // same x -> starts (neg) before ends (0); taller start first
    events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
                                       : Integer.compare(a[1], b[1]));

    // max-heap of {height, end}; ground sentinel never expires
    PriorityQueue<int[]> live = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
    live.offer(new int[]{0, Integer.MAX_VALUE});

    List<List<Integer>> res = new ArrayList<>();
    int prevH = 0;

    for (int[] e : events) {
        int x = e[0];
        // 1) LAZY EVICT  (size > 1 protects the sentinel: R can be 2^31 - 1 == Integer.MAX_VALUE)
        while (live.size() > 1 && live.peek()[1] <= x) live.poll();
        // 2) INSERT
        if (e[1] < 0) live.offer(new int[]{-e[1], e[2]});
        // 3) READ
        int curH = live.peek()[0];
        if (curH != prevH) {
            res.add(Arrays.asList(x, curH));
            prevH = curH;
        }
    }
    return res;
}

Why the ground sentinel (0, ∞)? It guarantees the heap is never empty, so live[0] is always readable — when the last building ends, the top becomes height 0 and we correctly emit the “skyline drops to ground” key point. ⚠️ In Java the sentinel end is Integer.MAX_VALUE, and LC 218 allows a real R to equal it (0 <= left < right <= 2^31 - 1), so the eviction loop must be guarded with live.size() > 1 — otherwise the sentinel is popped and the next peek() NPEs on an empty heap. Python’s float('inf') needs no guard.

Gotchas

  • ⚠️ Event tie-breaking is the whole problem. At a shared x, process starts before ends (otherwise a building that starts exactly where another ends produces a spurious dip), and taller starts before shorter starts (otherwise a spurious step appears).
  • ⚠️ Deduplicate end events (set(...)) or just accept duplicates — they are harmless because the emitted height won’t change twice.
  • ⚠️ Only emit when the height actually changes, otherwise you output redundant key points.

Variation — LC 1851 Minimum Interval to Include Each Query: answer queries offline. Sort intervals by left and queries ascending; for each query q push every interval with left <= q into a min-heap keyed by interval length (right-left+1, right), then lazy-pop while heap[0].right < q. The top is the smallest interval covering q. Same three steps — insert, lazy evict, read — with the sweep driven by queries instead of x-coordinates.

3) Bounded “Regret” Heap — Keep the k Best, Pay for the Rest Priority 4 of 5 — High value — a gap here costs you rounds

Core Idea

You have k free passes (ladders, VIP slots, one-time discounts) and a budget for everything else, and you must decide online, before seeing future costs. The trick:

text
Optimistically give EVERY cost a free pass.
Keep a MIN-HEAP of the costs currently holding a pass, capped at size k.
When the heap overflows -> the SMALLEST pass-holder is evicted and paid from the budget.

At any moment the heap holds exactly the k largest costs seen so far — which is precisely the optimal assignment of the k free passes for the prefix processed so far. No backtracking needed.

Contrast with LC 630 Course Schedule III (max-heap replace: evict the largest item when you overrun) — same “commit then regret” idea, opposite comparator. Here we evict the smallest, because a free pass is wasted on a cheap item.

Worked example — LC 1642 Furthest Building You Can Reach

Each upward step d = heights[i+1] - heights[i] > 0 costs either one ladder or d bricks.

python
# python
# LC 1642 - Furthest Building You Can Reach
# time = O(N log L), space = O(L)   (L = ladders)
# IDEA: give every climb a ladder; when > L ladders are in use, downgrade the SMALLEST to bricks
import heapq

class Solution(object):
    def furthestBuilding(self, heights, bricks, ladders):
        ladder_jumps = []   # min-heap of the climbs currently using a ladder

        for i in range(len(heights) - 1):
            d = heights[i + 1] - heights[i]
            if d <= 0:
                continue                       # going down / flat is free

            heapq.heappush(ladder_jumps, d)    # optimistically use a ladder

            if len(ladder_jumps) > ladders:
                # the smallest climb loses its ladder and is paid with bricks
                bricks -= heapq.heappop(ladder_jumps)
                if bricks < 0:
                    return i                   # stuck standing on building i

        return len(heights) - 1
java
// java
// LC 1642 - Furthest Building You Can Reach
// time = O(N log L), space = O(L)   (L = ladders)
// IDEA: min-heap of climbs holding a ladder, capped at L; evicted (smallest) climb costs bricks
public int furthestBuilding(int[] heights, int bricks, int ladders) {
    PriorityQueue<Integer> ladderJumps = new PriorityQueue<>();   // min-heap

    for (int i = 0; i + 1 < heights.length; i++) {
        int d = heights[i + 1] - heights[i];
        if (d <= 0) continue;

        ladderJumps.offer(d);

        if (ladderJumps.size() > ladders) {
            bricks -= ladderJumps.poll();       // smallest climb downgraded to bricks
            if (bricks < 0) return i;
        }
    }
    return heights.length - 1;
}

Gotchas

  • ⚠️ Return i (the building you are standing on), not i+1, when the bricks run out.
  • ⚠️ ladders == 0 must still work: the heap overflows immediately on every climb, so every climb is paid with bricks — no special case needed.
  • ⚠️ Skip non-positive d before pushing, otherwise zero/negative climbs occupy ladders.

Variation — LC 1792 Maximum Average Pass Ratio: the heap is keyed by marginal gain, not by raw value. Push (pass+1)/(total+1) - pass/total for each class into a max heap; each extra student goes to the class with the biggest gain, then that class is re-pushed with its updated gain. Key insight: the gain is monotonically decreasing per class, so a greedy heap pick is optimal.

4) Greedy with Regret — Undo the Worst Past Decision Priority 4 of 5 — High value — a gap here costs you rounds

When: you must scan forward taking items, and it is only later that you discover you took too many / too much. Take everything optimistically, keep the taken items in a heap, and when you violate the budget undo the worst decision so far (poll()). Formally an exchange argument — swapping in the best deferred item never hurts.

java
// java
// LC 871 - Minimum Number of Refueling Stops
// IDEA: drive as far as fuel allows, pushing every passed station's fuel into a MAX-heap
//       ("I could have stopped there"); when stuck, retroactively refuel at the biggest one
// time = O(n log n), space = O(n)
public int minRefuelStops(int target, int startFuel, int[][] stations) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    int fuel = startFuel, i = 0, stops = 0;

    while (fuel < target) {
        // every station within reach becomes a "regret option"
        while (i < stations.length && stations[i][0] <= fuel) {
            pq.offer(stations[i][1]);
            i++;
        }
        if (pq.isEmpty()) return -1;    // no option left -> unreachable
        fuel += pq.poll();              // retroactively take the biggest tank
        stops++;
    }
    return stops;
}
python
# python
# LC 871 - Minimum Number of Refueling Stops
# IDEA: max-heap of fuel at already-passed stations; refuel from it only when stuck
# time = O(n log n), space = O(n)
import heapq

def minRefuelStops(target, startFuel, stations):
    pq = []                              # max-heap via negation
    fuel, i, stops = startFuel, 0, 0

    while fuel < target:
        while i < len(stations) and stations[i][0] <= fuel:
            heapq.heappush(pq, -stations[i][1])
            i += 1
        if not pq:
            return -1
        fuel -= heapq.heappop(pq)        # -(-max) => add the largest tank
        stops += 1

    return stops

Second solution for LC 871 — DP over the number of stops, O(n²). reach[t] is the farthest position reachable with exactly t stops; station i can extend every t whose reach already covers it. It needs no exchange argument, which is its use: it is the answer to give if you cannot justify the greedy. The heap is V0 because it is O(n log n) and the regret argument is short.

python
# python
# LC 871 - Minimum Number of Refueling Stops (DP)
# IDEA: reach[t] = farthest position with exactly t stops; relax t backwards so each station is used once
# time = O(n^2), space = O(n)
def minRefuelStops_dp(target, startFuel, stations):
    n = len(stations)
    reach = [startFuel] + [0] * n   # reach[t] = farthest position with exactly t stops
    for i, (pos, fuel) in enumerate(stations):
        for t in range(i, -1, -1):  # backwards: station i is used at most once
            if reach[t] >= pos:
                reach[t + 1] = max(reach[t + 1], reach[t] + fuel)
    for t in range(n + 1):
        if reach[t] >= target:
            return t
    return -1

Traps (LC 871)

  • Refuelling at the nearest passed station instead of the largest: the exchange argument only holds for the largest tank.
  • Stations are already sorted by position; sorting again is harmless, sorting by fuel is wrong.
  • startFuel >= target needs zero stops even with no stations: check fuel < target before popping.

Variation: Course Schedule III (LC 630) — twist: sort by deadline, take every course, and the moment time > deadline drop the longest course taken so far. Dropping the longest never breaks feasibility of the earlier deadlines.

java
// java
// LC 630 - Course Schedule III
// IDEA: sort by deadline; greedily take each course, and if the schedule overflows,
//       regret the longest course already taken (max-heap of durations)
// time = O(n log n), space = O(n)
public int scheduleCourse(int[][] courses) {
    Arrays.sort(courses, (a, b) -> Integer.compare(a[1], b[1]));   // by deadline
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    int time = 0;

    for (int[] c : courses) {
        time += c[0];
        pq.offer(c[0]);
        if (time > c[1]) time -= pq.poll();   // undo the longest one taken
    }
    return pq.size();
}
python
# python
# LC 630 - Course Schedule III
# IDEA: sort by deadline; take every course, and regret the longest one when it overruns
# time = O(n log n), space = O(n)
import heapq

def scheduleCourse(courses):
    courses.sort(key=lambda x: x[1])   # sort by deadline
    heap = []   # max-heap (store negated durations)
    time = 0
    for duration, deadline in courses:
        if time + duration <= deadline:
            time += duration
            heapq.heappush(heap, -duration)
        elif heap and -heap[0] > duration:
            # Replace longest course with current shorter one
            time += duration + heap[0]   # heap[0] is negative
            heapq.heapreplace(heap, -duration)
    return len(heap)

Key insight: Replacing a longer course with a shorter one never increases total time but may allow fitting more courses.

Variation: Furthest Building You Can Reach (LC 1642) — twist: the heap holds the climbs currently assigned to ladders (min-heap). Once ladders run out, the smallest laddered climb is demoted to bricks — so ladders always end up on the largest climbs. Code: 3) Bounded “Regret” Heap above.

Variation: IPO (LC 502) — two heaps instead of one: a locked list sorted by capital and an available max-heap by profit. Unlock everything you can currently afford, then take the single best available project; repeat k times.

python
# python
# LC 502 - IPO
# IDEA: unlock projects by capital, then greedily take the highest profit available
# time = O(n log n), space = O(n)
import heapq

def findMaximizedCapital(k, w, profits, capital):
    # Min-heap by capital (locked projects)
    locked = sorted(zip(capital, profits))
    # Max-heap by profit (available projects, negate for max-heap)
    available = []
    i = 0
    for _ in range(k):
        # Unlock all projects we can afford
        while i < len(locked) and locked[i][0] <= w:
            heapq.heappush(available, -locked[i][1])
            i += 1
        if not available: break
        w += -heapq.heappop(available)   # pick highest profit
    return w

Key Observations:

  • Signature of the pattern: “minimum number of X” / “maximum count of Y” where a decision can be revised later at no cost.
  • Heap direction encodes the regret: max-heap when you want to undo the worst / take the best deferred option (LC 871, 630); min-heap when you want to demote the cheapest of a limited premium resource (LC 1642).
  • Contrast with heap.md § Template 6 Min-Heap of End Times: interval scheduling never revises a decision; regret-greedy is built entirely on revising them.

5) Two Heaps as Resource Pools (free pool + busy pool) Priority 4 of 5 — High value — a gap here costs you rounds

Core Idea

Not every “two heaps” problem is a median problem. A very common variant is a resource allocator, where the two heaps are ordered by different keys:

text
freeHeap = min-heap by RESOURCE ID     -> "which resource do I hand out next?"
busyHeap = min-heap by RELEASE TIME    -> "which resource comes back first?"

The loop is always the same three steps, in this exact order:

text
1. RELEASE : while busyHeap and busyHeap.top.releaseTime <= now:  move it to freeHeap
2. ASSIGN  : take freeHeap.top   (or mint a brand-new resource if the pool is empty)
3. OCCUPY  : push (releaseTime, resourceId) into busyHeap

Worked example — LC 1942 The Number of the Smallest Unoccupied Chair

python
# python
# LC 1942 - The Number of the Smallest Unoccupied Chair
# time = O(N log N), space = O(N)
# IDEA: free chairs = min-heap by chair id; occupied = min-heap by leaving time; release -> assign
import heapq

class Solution(object):
    def smallestChair(self, times, targetFriend):
        # process friends in ARRIVAL order, but remember original index
        order = sorted(range(len(times)), key=lambda i: times[i][0])

        free = []          # min-heap of chair ids
        busy = []          # min-heap of (leave_time, chair_id)
        next_chair = 0

        for i in order:
            arrive, leave = times[i]

            # 1) RELEASE : chair frees exactly AT leave time -> `<=`
            while busy and busy[0][0] <= arrive:
                _, c = heapq.heappop(busy)
                heapq.heappush(free, c)

            # 2) ASSIGN : smallest free id, else mint a new chair
            if free:
                chair = heapq.heappop(free)
            else:
                chair = next_chair
                next_chair += 1

            if i == targetFriend:
                return chair

            # 3) OCCUPY
            heapq.heappush(busy, (leave, chair))

        return -1
java
// java
// LC 1942 - The Number of the Smallest Unoccupied Chair
// time = O(N log N), space = O(N)
// IDEA: free chairs = min-heap by id; busy chairs = min-heap by leaving time
public int smallestChair(int[][] times, int targetFriend) {
    int n = times.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(times[a][0], times[b][0]));   // by arrival

    PriorityQueue<Integer> free = new PriorityQueue<>();                    // chair ids
    PriorityQueue<int[]> busy = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // {leave, chair}
    int nextChair = 0;

    for (int i : order) {
        int arrive = times[i][0], leave = times[i][1];

        // 1) RELEASE
        while (!busy.isEmpty() && busy.peek()[0] <= arrive) {
            free.offer(busy.poll()[1]);
        }
        // 2) ASSIGN
        int chair = free.isEmpty() ? nextChair++ : free.poll();

        if (i == targetFriend) return chair;

        // 3) OCCUPY
        busy.offer(new int[]{leave, chair});
    }
    return -1;
}

Gotchas

  • ⚠️ Sort by arrival, but keep the original index — the answer is asked about friend targetFriend, not about the k-th arrival.
  • ⚠️ <= in the release step: a chair vacated at time t is available to someone arriving at t.
  • ⚠️ Release before assigning, or you mint chairs that did not need to exist.

Variations of this template:

LC Problem The twist
1606 Find Servers That Handled Most Number of Requests Free pool must be searched circularly from index i % k — use two free heaps (ids >= i%k and ids < i%k), or a TreeSet with ceiling(). Busy heap is keyed by finish time as usual.
1801 Number of Orders in the Backlog Two heaps of opposite polarity that consume each other: buy = max-heap by price, sell = min-heap by price. Each new order is matched against the other heap while the prices cross; the remainder is pushed.
2102 Sequentially Ordinal Rank Tracker Two heaps split the stream around the query pointer: max-heap for “already returned / better” and min-heap for the rest; each get() moves one element across the boundary.

6) Sort by One Criterion + Fixed-Size Heap on the Other

When: the objective is a product/combination of two attributes, e.g. cost = (sum of A over the chosen k) * (max of B over the chosen k). Sort by B so that iterating fixes the “max B” factor, then keep a size-k heap over A to minimise/maximise the sum. This is the two-attribute cousin of the Template 1: Size-k Min-Heap.

java
// java
// LC 857 - Minimum Cost to Hire K Workers
// IDEA: pay ratio = wage/quality; sort workers by ratio ascending -> the current worker's
//       ratio is the ratio the whole group must be paid. Keep the k SMALLEST qualities
//       with a max-heap; answer = min(sumQuality * ratio).
// time = O(n log n), space = O(n)
public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
    int n = quality.length;
    double[][] workers = new double[n][2];             // [ratio, quality]
    for (int i = 0; i < n; i++) {
        workers[i] = new double[]{(double) wage[i] / quality[i], quality[i]};
    }
    Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));

    PriorityQueue<Double> pq = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    double sumQ = 0, res = Double.MAX_VALUE;

    for (double[] w : workers) {
        pq.offer(w[1]);
        sumQ += w[1];
        if (pq.size() > k) sumQ -= pq.poll();          // drop the largest quality
        if (pq.size() == k) res = Math.min(res, sumQ * w[0]);
    }
    return res;
}
python
# python
# LC 857 - Minimum Cost to Hire K Workers
# IDEA: sort by wage/quality ratio; max-heap keeps the k smallest qualities seen so far
# time = O(n log n), space = O(n)
import heapq

def mincostToHireWorkers(quality, wage, k):
    workers = sorted((w / q, q) for q, w in zip(quality, wage))
    pq, sum_q, res = [], 0, float('inf')

    for ratio, q in workers:
        heapq.heappush(pq, -q)          # max-heap via negation
        sum_q += q
        if len(pq) > k:
            sum_q += heapq.heappop(pq)  # pop returns -max -> adding it subtracts
        if len(pq) == k:
            res = min(res, sum_q * ratio)

    return res

Variation: Maximum Performance of a Team (LC 1383) — same shape, opposite directions: sort by efficiency descending (the current efficiency is the team minimum), keep a min-heap of speeds of size k so the sum is maximised. The team may have at most k members, so every prefix is a candidate, not only full teams.

python
# python
# LC 1383 - Maximum Performance of a Team
# IDEA: sort by efficiency descending; min-heap keeps the k fastest so far; current eff is the team min
# time = O(n log n), space = O(n)
import heapq

def maxPerformance(n, speed, efficiency, k):
    engineers = sorted(zip(efficiency, speed), reverse=True)   # efficiency high -> low
    heap = []          # min-heap of the speeds on the team
    speed_sum = 0
    best = 0
    for eff, spd in engineers:
        heapq.heappush(heap, spd)
        speed_sum += spd
        if len(heap) > k:
            speed_sum -= heapq.heappop(heap)   # drop the slowest
        best = max(best, speed_sum * eff)      # eff is the team minimum
    return best % (10**9 + 7)
java
// java
// LC 1383 - Maximum Performance of a Team
// IDEA: sort by efficiency descending; min-heap keeps the k fastest so far; current eff is the team min
// time = O(n log n), space = O(n)
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
    int[][] engineers = new int[n][2];                   // {efficiency, speed}
    for (int i = 0; i < n; i++) {
        engineers[i] = new int[]{efficiency[i], speed[i]};
    }
    Arrays.sort(engineers, (a, b) -> Integer.compare(b[0], a[0]));   // efficiency high -> low
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();          // speeds on the team
    long speedSum = 0;
    long best = 0;
    for (int[] eng : engineers) {
        minHeap.offer(eng[1]);
        speedSum += eng[1];
        if (minHeap.size() > k) {
            speedSum -= minHeap.poll();                  // drop the slowest
        }
        best = Math.max(best, speedSum * eng[0]);        // eng[0] is the team minimum
    }
    return (int) (best % 1_000_000_007);
}
text
speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
sorted by efficiency desc: (9,1) (7,5) (5,2) (4,10) (3,3) (2,8)

(9,1)   heap=[1]      sum=1    perf= 9
(7,5)   heap=[1,5]    sum=6    perf=42
(5,2)   heap=[2,5]    sum=7    perf=35   (1 dropped)
(4,10)  heap=[5,10]   sum=15   perf=60   <- answer

Key Observations:

  • Sort fixes the multiplicative factor, the heap optimises the additive factor. Recognising which attribute to sort by is the entire problem.
  • Take the modulo only at the very end (LC 1383) — applying it inside the loop breaks the max comparison.
  • The heap must be the opposite direction of what you keep: keep k smallest → max-heap; keep k largest → min-heap (same rule as the Template 1: Size-k Min-Heap).

7) Min-Heap Best-First Search on a Grid

When: a grid where the next cell to expand is not the nearest in steps but the cheapest/lowest so far — Dijkstra with the grid as an implicit graph. Template 5 assumes an adjacency list; this variant seeds the heap from a boundary and expands inward.

java
// java
// LC 407 - Trapping Rain Water II
// IDEA: water level is decided by the lowest wall on the border. Seed a min-heap with the
//       whole border, always expand the lowest cell; an inner neighbour lower than the
//       current level traps (level - height) and then becomes a wall of that level.
// time = O(m*n*log(m*n)), space = O(m*n)
public int trapRainWater(int[][] heightMap) {
    int m = heightMap.length, n = heightMap[0].length;
    if (m < 3 || n < 3) return 0;

    boolean[][] seen = new boolean[m][n];
    // min-heap of {height, row, col}
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
                pq.offer(new int[]{heightMap[i][j], i, j});
                seen[i][j] = true;
            }
        }
    }

    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int water = 0;

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int level = cur[0], r = cur[1], c = cur[2];

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n || seen[nr][nc]) continue;
            seen[nr][nc] = true;
            water += Math.max(0, level - heightMap[nr][nc]);          // trapped water
            pq.offer(new int[]{Math.max(level, heightMap[nr][nc]), nr, nc});
        }
    }
    return water;
}
python
# python
# LC 407 - Trapping Rain Water II
# IDEA: min-heap seeded with the border; pop the lowest wall, water on a lower neighbour
#       = level - height, and the neighbour joins the border at max(level, height)
# time = O(m*n*log(m*n)), space = O(m*n)
import heapq

def trapRainWater(heightMap):
    if not heightMap or len(heightMap) < 3 or len(heightMap[0]) < 3:
        return 0

    m, n = len(heightMap), len(heightMap[0])
    seen = [[False] * n for _ in range(m)]
    pq = []

    for i in range(m):
        for j in range(n):
            if i in (0, m - 1) or j in (0, n - 1):
                heapq.heappush(pq, (heightMap[i][j], i, j))
                seen[i][j] = True

    water = 0
    while pq:
        level, r, c = heapq.heappop(pq)
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc]:
                seen[nr][nc] = True
                water += max(0, level - heightMap[nr][nc])
                heapq.heappush(pq, (max(level, heightMap[nr][nc]), nr, nc))

    return water

Key Observations:

  • Popping the globally lowest boundary cell is what makes the greedy correct: water can only escape over the lowest wall, so that cell’s level is final.
  • Mark seen at push time, not at pop time, or cells get queued repeatedly.
  • Same skeleton, different priority key:
LC Problem Priority key pushed into the heap
407 Trapping Rain Water II max(current level, neighbour height) — the effective wall
778 Swim in Rising Water max(current level, neighbour height) — minimise the maximum cell on the path
1631 Path With Minimum Effort max(current effort, abs(height diff)) — minimax edge
1368 Minimum Cost to Make at Least One Valid Path in a Grid cost + (0 if arrow points at neighbour else 1) — 0/1 weights (a deque also works)
675 Cut Off Trees for Golf Event Trees must be cut shortest first: sort/heap the targets by height, then run a BFS between consecutive targets

8) Grid Shortest Path with Range Jumps

When: from cell (i, j) you may jump to any cell up to grid[i][j] to the right in its row, or down in its column, and the fewest cells visited is asked (LC 2617). BFS that enumerates every jump target is O(m·n·(m + n)). Instead, sweep the cells in row-major order: every cell that can reach (i, j) lies earlier in the same row or the same column, so keep one min-heap per row and one per column of (cells visited, index) for the cells already finalised.

Key point — an entry whose reach index + grid[...] falls short of the current column (or row) can never reach anything later in the sweep, so it is popped for good. The first entry that can reach is the minimum among all that can, because the heap orders by distance. This is lazy deletion with “expired by coordinate” as the staleness test.

Worked example — LC 2617 Minimum Number of Visited Cells in a Grid

python
# python
# LC 2617 - Minimum Number of Visited Cells in a Grid
# IDEA: row-major sweep; per-row and per-column min-heaps of (dist, index); pop entries whose
#       reach falls short of the current cell, the first one left gives dist + 1
# time = O(m*n*log(m+n)), space = O(m*n)
import heapq

def minimumVisitedCells(grid):
    m, n = len(grid), len(grid[0])
    dist = [[-1] * n for _ in range(m)]
    row_pqs = [[] for _ in range(m)]     # row_pqs[i]: (dist, col) of finalised cells in row i
    col_pqs = [[] for _ in range(n)]     # col_pqs[j]: (dist, row) of finalised cells in column j
    dist[0][0] = 1
    for i in range(m):
        for j in range(n):
            while row_pqs[i]:            # best cell to the left that still reaches column j
                d, prev_col = row_pqs[i][0]
                if prev_col + grid[i][prev_col] >= j:
                    if dist[i][j] == -1 or d + 1 < dist[i][j]:
                        dist[i][j] = d + 1
                    break
                heapq.heappop(row_pqs[i])        # cannot reach j, so no later column either
            while col_pqs[j]:            # best cell above that still reaches row i
                d, prev_row = col_pqs[j][0]
                if prev_row + grid[prev_row][j] >= i:
                    if dist[i][j] == -1 or d + 1 < dist[i][j]:
                        dist[i][j] = d + 1
                    break
                heapq.heappop(col_pqs[j])
            if dist[i][j] != -1 and grid[i][j] > 0:   # reachable and can jump: offer it forward
                heapq.heappush(row_pqs[i], (dist[i][j], j))
                heapq.heappush(col_pqs[j], (dist[i][j], i))
    return dist[m - 1][n - 1]
java
// java
// LC 2617 - Minimum Number of Visited Cells in a Grid
// IDEA: row-major sweep; per-row and per-column min-heaps of {dist, index}; poll entries that
//       can no longer reach the current cell, the first one left gives dist + 1
// time = O(m*n*log(m+n)), space = O(m*n)
public int minimumVisitedCells(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, -1);

    List<PriorityQueue<int[]>> rowPQs = new ArrayList<>();   // {dist, col} per row
    List<PriorityQueue<int[]>> colPQs = new ArrayList<>();   // {dist, row} per column
    for (int i = 0; i < m; i++) rowPQs.add(new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])));
    for (int j = 0; j < n; j++) colPQs.add(new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])));

    dist[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            PriorityQueue<int[]> rowPQ = rowPQs.get(i);
            while (!rowPQ.isEmpty()) {
                int[] top = rowPQ.peek();
                if (top[1] + grid[i][top[1]] >= j) {     // still reaches column j
                    if (dist[i][j] == -1 || top[0] + 1 < dist[i][j]) dist[i][j] = top[0] + 1;
                    break;
                }
                rowPQ.poll();                            // cannot reach j, nor any later column
            }
            PriorityQueue<int[]> colPQ = colPQs.get(j);
            while (!colPQ.isEmpty()) {
                int[] top = colPQ.peek();
                if (top[1] + grid[top[1]][j] >= i) {
                    if (dist[i][j] == -1 || top[0] + 1 < dist[i][j]) dist[i][j] = top[0] + 1;
                    break;
                }
                colPQ.poll();
            }
            if (dist[i][j] != -1 && grid[i][j] > 0) {
                rowPQ.offer(new int[]{dist[i][j], j});
                colPQ.offer(new int[]{dist[i][j], i});
            }
        }
    }
    return dist[m - 1][n - 1];
}

Traps

  • The start counts as one visited cell: dist[0][0] = 1, and a 1×1 grid answers 1.
  • grid[i][j] == 0 cells are reachable but jump nowhere; pushing them is harmless, skipping them keeps the heaps small.
  • break on the first entry that reaches: entries below it have a larger distance, so looking further only costs time.
  • Java: an array of generic PriorityQueues needs an unchecked cast; a List of them avoids it.

9) Frequency Uniqueness — Greedy + Heap / HashSet

“Make every frequency distinct with the fewest deletions” (LC 1647) is heap § Template 2 with one added step: process counts from the largest down in a max-heap, and when the top ties with the next count, shave one off and push it back. It needs nothing from this sheet, so it is worked as a problem card in heap_examples.md § LC 1647, with the set-of-used-counts alternative named there.

Traps

  • A sort-based version that breaks at the first count shaved to 0 stops too early: 4,4,1,1,1 ("aebacabbbad") still has two 1s after the break, and returns 2 instead of 3.
  • LC 1481 (fewest distinct values after k removals) looks related but is the opposite greedy: remove the smallest counts whole — heap_examples.md § LC 1481.

10) Heap with Deduplication

python
# python
# IDEA: a set guards the heap so each value is pushed once (LC 264 generates duplicates otherwise)
# time = O(n log n), space = O(n)
import heapq

def solve_with_unique_heap(nums):
    heap = []
    seen = set()
    for num in nums:
        if num not in seen:
            heapq.heappush(heap, num)
            seen.add(num)
    return heap

Worked use: LC 264 Ugly Number II, where 2·3 and 3·2 would both push 6 — Dijkstra_examples § Variation B.

11) K-Way Merge Variants

Variations of Template 2 (same skeleton, different bookkeeping):

LC Problem Twist on the k-way merge
632 Smallest Range Covering Elements from K Lists Also track the max of the k heap elements; every pop gives a window [heap_min, running_max] that covers all lists — stop when any list is exhausted
355 Design Twitter The “k sorted lists” are the followees’ tweet lists (newest first); push each followee’s head into a max-heap by timestamp, pop 10 times
373 / 378 K Pairs with Smallest Sums / Kth Smallest in Sorted Matrix Lists are virtual rows of a sorted grid — see heap_examples.md § LC 373 / § LC 378
python
# python
# LC 632 - Smallest Range Covering Elements from K Lists
# IDEA: k-way merge frontier; window = [heap top, max of frontier]
# time = O(N log k), space = O(k)   N = total elements
import heapq

def smallestRange(nums):
    pq = [(row[0], i, 0) for i, row in enumerate(nums)]
    heapq.heapify(pq)
    cur_max = max(row[0] for row in nums)
    best = [pq[0][0], cur_max]

    while pq:
        val, i, j = heapq.heappop(pq)
        if cur_max - val < best[1] - best[0]:
            best = [val, cur_max]
        if j + 1 == len(nums[i]):
            break                      # a list is exhausted -> no more covering window
        nxt = nums[i][j + 1]
        cur_max = max(cur_max, nxt)
        heapq.heappush(pq, (nxt, i, j + 1))

    return best

Variation — LC 1439 Find the Kth Smallest Sum of a Matrix With Sorted Rows: instead of merging rows, merge row by row. Keep a running list of the k smallest sums built from the first r rows, then combine it with row r+1 using the same k-smallest-pairs trick as LC 373 (min-heap seeded with (prev[0] + row[0], i=0, j=0), expand (i+1, j) / (i, j+1), stop after k pops). Reduces an exponential search to O(m * k log k).

12) Lazy Deletion — the “removed counter” Flavour

When you can’t remove arbitrary elements from a heap, mark them as invalid and skip on pop.

This is the “removed counter” flavour. For the “hashmap of truth” flavour (value changed rather than element removed), see 1) Lazy Deletion and its worked example, LC 3092 Most Frequent IDs, in the same section.

python
# python
# IDEA: remove() only counts the value; pop() discards counted values when they reach the top
# time = O(log n) amortised per operation, space = O(n)
import heapq

class LazyHeap:
    def __init__(self):
        self.heap = []
        self.removed = {}   # val -> count of removed instances

    def push(self, val):
        heapq.heappush(self.heap, val)

    def remove(self, val):
        self.removed[val] = self.removed.get(val, 0) + 1

    def pop(self):
        while self.heap:
            val = self.heap[0]
            if self.removed.get(val, 0) > 0:
                heapq.heappop(self.heap)
                self.removed[val] -= 1
            else:
                return heapq.heappop(self.heap)
        return None

# Used in: LC 480 Sliding Window Median, LC 1825 Finding MK Average

Beyond the Binary Heap

Indexed Priority Queue

  • Allows decrease-key operation
  • Useful for Dijkstra optimization
  • Track element positions in heap

Fibonacci Heap

  • O(1) amortized insert, decrease-key
  • O(log n) extract-min
  • Complex implementation, rarely used

Binary Heap Variants

  • d-ary heap: Better cache performance
  • Binomial heap: Better merge operation
  • Pairing heap: Simple, good practical performance

When Not to Use

Most problems that look like they need a technique here are solved by a core card. Check these first.

Technique Looks needed when The simpler answer that usually suffices
§ 1 Lazy deletion a heap’s values change values only grow and a stale-but-larger entry is still a valid upper bound → no cleaning; or the window expires by index and needs one extreme → monotonic deque (monotonic_queue.md)
§ 1 two mirrored lazy heaps max and min of a changing set values are insert-only and never change once added → two running variables (not LC 2034: a later update overwrites an old price, and the running max would keep it); the language has an ordered map (TreeMap) and the interviewer accepts it
§ 2 Sweep + alive heap intervals and “at every x” only the count covering x → difference array, or heap § Template 6 for the peak
§ 3 Bounded regret heap “k free passes” no budget to pay from → the k largest is heap § Template 1
§ 4 Greedy with regret “minimum number of stops / maximum tasks” items are independent and sorting by deadline alone decides them → plain sort + greedy (greedy.md)
§ 5 Resource pools “assign rooms / servers” only how many are needed, not which id → heap § Template 6
§ 6 Sort + fixed-size heap two attributes, pick k the objective uses one attribute → heap § Template 1
§ 7 Grid best-first a weighted grid all moves cost 1 → BFS (bfs.md); an explicit graph → Dijkstra.md
§ 8 Range-jump grid each cell jumps far jumps are bounded by a small constant → BFS over the neighbours
§ 9 Frequency uniqueness “make counts distinct” it is the core card: heap § Template 2, or a set of used counts
§ 10 Heap with deduplication duplicates are pushed duplicates are harmless to the answer → pop and skip a value equal to the last one popped
§ 11 K-way merge variants several sorted sources the sources are real lists → heap § Template 3 as written
§ 12 Removed-counter lazy deletion values leave a two-heap window sortedcontainers.SortedList / TreeMap is allowed → an ordered multiset deletes directly

Summary & Quick Reference

Signal in the problem Pattern Section
a pushed value changed / was removed heap of candidates + hashmap of truth 1
both max and min over one mutating map two mirrored lazy heaps sharing the truth map 1
“where else is this idea?” — tombstones hash tables, LSM-trees, MVCC, GC, Dijkstra 1
“max/min over everything covering x” sweep + alive heap, evict by coordinate 2
“k ladders / k free upgrades” min-heap capped at k, pay for the evicted 3
“minimum number of stops / max courses” take everything, poll() the worst when stuck 4
“smallest free chair / server” free-by-id heap + busy-by-release-time heap 5
objective is sum(A) × max/min(B) sort by B, size-k heap over A 6
grid, cost is a minimax or accumulated weight Dijkstra on the implicit grid graph 7
each grid cell jumps to a range per-row / per-column PQ + lazy pop 8
“make all frequencies unique” max-heap decrement, or a used-frequency set 9
merge virtual / nested sorted sources k-way merge with a rebuilt frontier 11
Signal Pattern
“kth largest/smallest” Min-heap of size k
“top k frequent” Counter + nlargest / bucket sort
“median of stream” Two heaps (max + min)
“always pick best available with constraint” Greedy + max-heap (IPO pattern)
“fit maximum number of tasks/courses” Sort by deadline + replace heap
“remove arbitrary element from heap” Lazy deletion
“merge k sorted lists” Min-heap with (val, list_idx, elem_idx)

Complexity Comparison

Operation Binary Heap Sorted Array AVL Tree
Insert O(log n) O(n) O(log n)
Delete min/max O(log n) O(1) O(log n)
Peek min/max O(1) O(1) O(log n)
Search arbitrary O(n) O(log n) O(log n)
Build from array O(n) O(n log n) O(n log n)
← Back to Cheat Sheets Edit on GitHub →