Heap / Priority Queue

Heaps maintain a dynamic set of elements where you need the smallest or largest quickly. The invariant is that the top is always the extremum according to the heap order.

Pattern A: Keep top-k with a min-heap

Use when: you need the kth largest or top-k elements.

Invariant: heap size never exceeds k; it holds the k largest seen.

Skeleton:

for x in nums:
    push x
    if size > k: pop min
return heap.top

Problems:

• kth-largest-element-in-an-array.

Pattern B: Top-k frequent by count

Use when: you need the k most frequent items.

Invariant: heap orders by frequency.

Skeleton:

count frequencies
push (freq, value) into min-heap
if size > k: pop
return values in heap

Problems:

• top-k-frequent-elements.

Pattern C: Pair sums with index heap

Use when: you need k smallest pairs from two sorted arrays.

Invariant: heap holds the next candidate pair for each i.

Skeleton:

for i in 0..min(k, len(nums1))-1:
    push (nums1[i] + nums2[0], i, 0)
repeat k times:
    pop (sum, i, j)
    output (i,j)
    if j+1 < len(nums2): push (nums1[i] + nums2[j+1], i, j+1)

Problems:

• find-k-pairs-with-smallest-sums.

Pattern D: Streaming median (two heaps)

Use when: you need median after each insertion.

Invariant: max-heap holds lower half, min-heap holds upper half.

Skeleton:

add(x):
    if empty or x <= maxTop: push to maxHeap else push to minHeap
    rebalance so sizes differ by at most 1
median():
    if sizes equal: avg(maxTop, minTop) else top of larger heap

Problems:

• find-median-from-data-stream.

Pattern E: Feasible projects with max profit

Use when: you have a capital constraint and want max profit each step.

Invariant: max-heap stores all projects with capital <= current.

Skeleton:

sort projects by capital
for i in 1..k:
    while next capital <= current: push profit into max-heap
    if heap empty: break
    current += pop max profit

Problems:

• ipo.

When to use Heaps (checklist)

• You need repeated access to min/max while inserting/removing.
• You need top-k elements without full sorting.

Common failures (checklist)

• Using the wrong heap type (min vs max).
• Forgetting to rebalance two heaps.
• Pushing too many candidates in pair problems.

Problem mapping

• kth-largest-element-in-an-array: min-heap size k.
• top-k-frequent-elements: heap by frequency.
• find-k-pairs-with-smallest-sums: index heap expansion.
• find-median-from-data-stream: two-heap median.
• ipo: max profit among feasible projects.