Stacks, Queues & Heaps
Heap / Priority Queue
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
top kk largestk smallestmedianstreamclosestmerge k
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- “Top / Kth largest or smallest”?
- Running median or merging K sorted streams?
- Need the extreme element repeatedly, cheaply?
Classic problem
Min-Heap Insert — Insert into a min-heap: append at the end, then sift up by swapping with parent while the new node is smaller. Each swap costs O(log n).
Input: Start with [4,8,9,12] (valid min-heap), insert 3, then insert 1
Output: min = 1 — after two insertions with sift-up, the heap is [1,4,3,12,8,9].
Common pitfalls
Min-heap vs max-heap; choose the heap direction for the rank you keep.
Heap of size k for kth-largest, not full sort.