Heap Pattern for Problem Solving

When the Answer Is "Whatever Is Best Right Now"

A heap (priority queue) gives you the smallest (or largest) item in O(1) and lets you insert or remove in O(log n). The Heap page explains how it works inside. This page is about which problems want one.

THE SIGNAL:  you repeatedly need the current best / worst / earliest / closest
             item, while items keep being ADDED or REMOVED.

  sorted array:  min in O(1), but insert costs O(n)
  plain array:   insert in O(1), but min costs O(n)
  heap:          min in O(1), insert and remove-min in O(log n)  ← balanced

The Four Recurring Shapes

1. TOP K              keep only the k best seen so far
                      → min-heap of size k for the LARGEST k
                      → max-heap of size k for the SMALLEST k

2. K-WAY MERGE        combine k sorted sources in order
                      → heap of each source's current front item

3. TWO HEAPS          balance two halves, read the middle
                      → max-heap (lower half) + min-heap (upper half)

4. EVENT SCHEDULING   process by time, track what's still running
                      → min-heap of end times / next free moments

Shape 1: Top k

scores = [42, 17, 88, 63, 5, 91, 30, 77], k = 3
min-heap of size 3 (root = weakest of the current top 3):

42          heap {42}
17          heap {17, 42}
88          heap {17, 42, 88}
63          push → {17, 42, 63, 88} → too big, pop 17 → {42, 63, 88}
 5          push → pop 5 immediately             → {42, 63, 88}
91          push → pop 42                        → {63, 88, 91}
30          push → pop 30                        → {63, 88, 91}
77          push → pop 63                        → {77, 88, 91}

Top 3: 77, 88, 91.   Time O(n log k), space O(k).

The counter-intuitive part: the k largest live in a min-heap, because what you constantly need to know is the smallest member — the one to evict.

Shape 2: k-Way Merge

lists:  [1, 7, 12]   [3, 4, 15]   [2, 9]   [5]

heap holds one front per list: {1, 3, 2, 5}
pop 1 (list 0) → push 7           {2, 3, 5, 7}
pop 2 (list 2) → push 9           {3, 5, 7, 9}
pop 3 (list 1) → push 4           {4, 5, 7, 9}
...
merged: 1 2 3 4 5 7 9 12 15

N items total, k lists → O(N log k)

Shape 3: Two Heaps for a Running Median

stream: 5, 15, 1, 3, 8, 7

LOW = max-heap (smaller half)   HIGH = min-heap (larger half)
rule: every LOW value ≤ every HIGH value, and |LOW| = |HIGH| or |HIGH| + 1

add 5   LOW {5}            HIGH {}          median 5.0
add 15  LOW {5}            HIGH {15}        median (5+15)/2 = 10.0
add 1   LOW {5, 1}         HIGH {15}        median 5.0
add 3   LOW {3, 1}         HIGH {5, 15}     median (3+5)/2 = 4.0
add 8   LOW {5, 3, 1}      HIGH {8, 15}     median 5.0
add 7   LOW {5, 3, 1}      HIGH {7, 8, 15}  median (5+7)/2 = 6.0

Each insert is O(log n), and the median is read from the roots in O(1).

Shape 4: How Many Rooms?

meetings [start, end): [9,10) [9,12) [10,11) [11,13) [12,14) [10,12)

sorted by start; heap = end times of meetings in progress
[9,10)   heap {10}                    rooms 1
[9,12)   10 > 9, can't reuse          {10, 12}          rooms 2
[10,11)  10 ≤ 10 → reuse (pop 10)     {11, 12}
[10,12)  11 > 10, can't reuse         {11, 12, 12}      rooms 3
[11,13)  11 ≤ 11 → reuse              {12, 12, 13}
[12,14)  12 ≤ 12 → reuse              {12, 13, 14}

Answer: 3 rooms (the most ever in use at once)

Code: All Four Shapes

Output:
top 3 of [42, 17, 88, 63, 5, 91, 30, 77]: [77, 88, 91]
merged: [1, 2, 3, 4, 5, 7, 9, 12, 15]
running medians: 5.0 10.0 5.0 4.0 5.0 6.0
rooms needed: 3

Heap or Something Else?

How to Spot It

✓ "k largest / k smallest / k closest / k most frequent"
✓ "merge k sorted ..."
✓ "median of a stream" / "balance two halves"
✓ "at any moment, process the earliest-ending / cheapest / highest-priority item"
✓ A greedy rule that needs "the current best" again and again
  (joining ropes cheapest-first, scheduling by deadline, CPU task queues)

Complexity

Common Mistakes

Using a max-heap for the k largest. It works only if you push everything (O(n) memory) and pop k times. The size-k min-heap is the streaming-friendly version.

Forgetting Python's heapq is a min-heap only. Push negated values (or (−priority, item) tuples) for max-heap behaviour.

Comparing tuples with uncomparable items. In Python, (value, list_obj) crashes on ties when lists can't be compared. Add a tie-breaker like the list index: (value, i, idx).

Not rebalancing both directions in the two-heap median — the sizes drift and the roots stop being the middle values.

Sorting meetings by end time for room counting. Rooms are assigned as meetings start, so process them by start time. Sorting by end (the right order for the greedy "most non-overlapping" problem) gives wrong room counts here.

Interview Questions

Q: Find the k most frequent words in a large list. What's your approach?

Count frequencies with a hash map, then keep a min-heap of size k ordered by (frequency, then reverse alphabetical for ties). For each word, push and pop if the heap exceeds k. Total O(n + u log k), where u is the number of distinct words. Finally, pop all and reverse to list the most frequent first.

Q: Why does the room-counting heap only need one pop per meeting?

Meetings are processed by start time. If the earliest-ending running meeting has finished, reusing its room keeps the heap size unchanged; if not, no meeting has finished and a new room is required. Other finished meetings remain in the heap, but they never cause an overcount — their rooms get reused by later meetings one at a time — so the maximum heap size still equals the true peak.

Q: How does the two-heap approach handle deleting values (e.g. a sliding-window median)?

Heaps don't support efficient arbitrary deletion, so use lazy deletion: record values to delete in a hash map, and discard them when they surface at a heap's root. Track the "logical" sizes separately for balancing. Each operation stays O(log n) amortised.

Summary

• ›Reach for a heap when you repeatedly need the current best while items come and go.
• ›Top k largest → min-heap of size k (evict the weakest).
• ›k-way merge → heap of fronts, O(N log k).
• ›Running median → two heaps, balanced within one element.
• ›Scheduling → min-heap of end times; peak heap size = resources needed.

Next, Monotonic Stack & Queue keeps values in sorted order as they arrive, answering "next greater" and "sliding window maximum" questions in O(n) total.