Heaps & Priority Queues — Master Recap & Cheatsheet

Heaps Section Complete — 46 Problems (421–466)

7 Core Heap Patterns

Pattern 1 — Top K with Fixed-Size Heap

# K largest: use min-heap of size K
heap = []
for n in nums:
    heapq.heappush(heap, n)
    if len(heap) > k:
        heapq.heappop(heap)
return heap  # k largest elements, heap[0] = kth largest

# K smallest: use max-heap of size K (negate values)

Pattern 2 — Two Heaps (Dynamic Median)

lo, hi = [], []  # lo=max-heap (negate), hi=min-heap
def add(num):
    heapq.heappush(lo, -num)
    heapq.heappush(hi, -heapq.heappop(lo))
    if len(lo) < len(hi):
        heapq.heappush(lo, -heapq.heappop(hi))

def median():
    if len(lo) > len(hi): return -lo[0]
    return (-lo[0] + hi[0]) / 2

Pattern 3 — K-way Merge

# Merge k sorted lists/streams
heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
heapq.heapify(heap)
while heap:
    val, i, j = heapq.heappop(heap)
    result.append(val)
    if j + 1 < len(lists[i]):
        heapq.heappush(heap, (lists[i][j+1], i, j+1))

Pattern 4 — Greedy + Max-Heap (Scheduling)

# Task scheduler, reorganize string, course schedule III
# Key: sort by constraint, use max-heap for greedy choice
import heapq
heap = [-freq for freq in frequencies]  # max-heap
heapq.heapify(heap)
while heap:
    top = -heapq.heappop(heap)
    # ... greedy decision

Pattern 5 — Retroactive Greedy (Min-Heap)

# Furthest building, minimum refueling stops
# Commit greedily, fix up later with heap
heap = []  # store ladder-climbs or gas stations
for step in steps:
    heap.push(step)
    if over_budget:
        use_worst = heap.pop()  # replace with bricks/fuel
        adjust_budget

Pattern 6 — Multi-pointer DP (Ugly Numbers)

# K sorted streams, pick minimum each step
ptrs = [0] * k
ugly = [1]
for _ in range(n - 1):
    next_val = min(ugly[ptrs[j]] * primes[j] for j in range(k))
    ugly.append(next_val)
    for j in range(k):
        if ugly[ptrs[j]] * primes[j] == next_val:
            ptrs[j] += 1

Pattern 7 — Two-Heap with Lazy Deletion

# Sliding window median, dynamic median with deletions
trash = defaultdict(int)
def remove(val, is_lo):
    trash[val] += 1
    # size adjustments
    # on access: skip trashed elements at heap tops

Problem Index

#	Title	Pattern	Difficulty
421	Kth Largest in Stream	Top K	Easy
422	Last Stone Weight	Max-heap sim	Easy
423	Relative Ranks	Sort	Easy
424	K Closest Elements	Binary search	Medium
425	Kth Largest Element	Quickselect/heap	Medium
426	Top K Frequent	Bucket/heap	Medium
427	Sort Characters by Freq	Freq+heap	Medium
428	K Closest Points	Top K	Medium
429	Task Scheduler	Math/greedy	Medium
430	Reorganize String	Greedy+heap	Medium
431	Find Median from Stream	Two heaps	Hard
432	Sliding Window Median	Two heaps+lazy	Hard
433	Merge K Sorted Lists	K-way merge	Hard
434	Kth Smallest in Matrix	Heap/BS	Medium
435	K Pairs Smallest Sums	K-way merge	Medium
436	Ugly Number II	Multi-ptr DP	Medium
437	Course Schedule III	Greedy+heap	Hard
438	Meeting Rooms II	Scheduling	Medium
439	Min Cost Connect Sticks	Huffman	Medium
440	IPO	Two heaps	Hard
441	Car Pooling	Diff array	Medium
442	Furthest Building	Retroactive greedy	Medium
443	Process Tasks Servers	Two heaps	Medium
444	Trapping Rain Water II	BFS+min-heap	Hard
445	Swim in Rising Water	Dijkstra	Hard
446	Smallest Range K Lists	K-way merge	Hard
447	Super Ugly Number	Multi-ptr	Medium
448	Min Refueling Stops	Retroactive greedy	Hard
449	Design Twitter	K-way merge	Medium
450	Ugly Number III	Binary search + IE	Medium
451	Max Performance Team	Greedy+heap	Hard
452	Longest Happy String	Greedy+heap	Medium
453	Max Frequency Stack	Freq buckets	Hard
454	Minimize Deviation	Greedy+heap	Hard

Complexity Summary

Operation	Min-Heap/Max-Heap
Build (heapify)	O(n)
Push	O(log n)
Pop	O(log n)
Peek/top	O(1)
Search	O(n)
Delete arbitrary	O(n) or O(log n) with lazy

Key Rules

Top K largest: min-heap of size k (evict smallest)
Top K smallest: max-heap of size k (evict largest)
Median: two heaps (lo max-heap, hi min-heap), sizes differ by ≤ 1
Merge K sorted: min-heap with (val, list_idx, elem_idx)
Greedy scheduling: sort by constraint (deadline, start), heap for best choice
Python max-heap: negate values (heapq is min by default)
Lazy deletion: when you can't efficiently remove from middle — use tombstone map

Python Max-Heap Patterns

# Max-heap for integers
heap = [-n for n in nums]
heapq.heapify(heap)
max_val = -heapq.heappop(heap)

# Max-heap for tuples
heapq.heappush(heap, (-priority, item))
priority, item = -val, item = heapq.heappop(heap)

# heapreplace: more efficient pop+push when heap non-empty
heapq.heapreplace(heap, new_val)  # pops min, pushes new_val