Heap / Priority Queue

Learning Outcome

Top K, two heaps, scheduling, merge streams, and event selection.

Pattern Recognition

Intuition

Use a heap when the next item to process is always the smallest, largest, earliest, or most urgent candidate.

Exact Practice Question Names

• Top K Frequent Elements
• K Closest Points to Origin
• Find Median from Data Stream
• Meeting Rooms III
• Merge K Sorted Lists
• Single-Threaded CPU

Interview Approach

1. Name the exact family.
2. Write the invariant or state.
3. Pick the standard container or recurrence.
4. Dry-run the smallest example.
5. State complexity and one follow-up.

Pseudocode

identify pattern
initialize state/container
for each input unit:
  update state safely
  update answer when invariant is valid
return answer
  

Sample Dry Run

Take the smallest Heap / Priority Queue example, track the state after every operation, and verify the final answer before coding.

Edge Cases

• Empty or single-item input
• Duplicate values
• Boundary constraints
• Large values requiring long/int64

Common Mistakes

• Memorizing code without naming the invariant
• Skipping the brute-force baseline
• Not explaining why the optimized approach is correct

Complexity

Java, C++ and Python Notes

• Java: prefer explicit classes and clear helper methods over clever one-liners.
• C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
• Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

• Name the pattern before coding.
• State the invariant or DP state in one sentence.
• Dry-run the smallest non-trivial example.
• Close with time and space complexity.