Day 50 — Revision: Heap week

Revision day · heap week · blank-file recall

Tonight's goal: prove you can choose the heap shape from memory, then re-solve three weak heap problems from a blank file with no hints.

Tonight's protocol

Adapted from Lesson 26 — How to Run a Revision Day.

  1. 0:00-0:04: Do the warm-up MCQs. Do not open notes, editor history, hints, or videos.
  2. 0:04-0:05: Pick your three weakest problems from the menu. For each menu item, answer: min-heap or max-heap, and what lives in it?
  3. 0:05-0:30: Problem 1. Open a blank file, say the pattern name, brute force, target complexity, then code. Only run one or run two counts.
  4. 0:30-0:55: Problem 2. Same rules: blank file, no hints, first or second run only.
  5. 0:55-1:20: Problem 3. If the second run still fails, stop counting it as revised and log the cause.
  6. 1:20-1:30: Compare only the failed or shaky attempts. Write one line: WA: <root cause>, then add that problem to the next revision queue.

The problem menu

Pick your three weakest from this menu. Re-solve from a blank file, no hints.

ProblemPattern nameHeap drill before coding
Kth Largest Element Heap top-k Min-heap; the k largest values seen so far.
Top K Frequent Elements Heap top-k by frequency Min-heap; (count, value) pairs for the current top k.
Merge K Sorted Lists K-way merge heap Min-heap; one current head from each unfinished list.
Find Median from Data Stream Two heaps Max-heap lower half, min-heap upper half.
Task Scheduler Heap scheduling with cooldown Max-heap of available counts; queue holds cooling tasks.

Warm-up MCQs

1. For Kth Largest, what heap choice matches the invariant?

2. A Top K Frequent attempt pushes (-count, value), then pops past k. What breaks?

3. Which heap contents keep Merge K Sorted Lists honest?

4. What split makes the median available after updates?

5. What does the heap choose from during Task Scheduler?

6. Why does Merge K use O(N log k) time?

Self-check gate

Pass tonight if

All three chosen problems compile and pass on run one or two, and you can answer min-heap or max-heap, and what lives in it? for all five menu problems without notes.

Failure path: if any attempt fails after run two, or any heap drill answer is unclear, write WA: <root cause> and add that exact problem to the next revision queue.