How a heap works (in 60 seconds)
A heap is a complete binary tree that maintains the heap property: in a min-heap, every parent is ≤ its children. The top (root) is always the minimum. Insert: O(log n) — add at the bottom, bubble up. Extract-min: O(log n) — swap root with last, remove last, bubble down. Peek: O(1). Use a max-heap (negate values in languages with only min-heap) for top-K largest. Python: heapq (min-heap only). Java: PriorityQueue (min by default). C++: priority_queue (max by default, use greater<int> for min).
Pattern 1: Top-K elements
Find the K largest / K smallest / K most frequent. Approach: maintain a heap of size K. For K largest: use a min-heap of size K — if current element > heap top, pop and push. After all elements, heap contains K largest. Time: O(n log k). For K most frequent: count frequencies with a hash map, then heap by frequency. Key problems: Kth Largest Element in Array (LC 215), Top K Frequent Elements (LC 347), K Closest Points to Origin (LC 973), Find Kth Largest in a Stream (LC 703).
Pattern 2: Merge K sorted structures
Classic pattern: you have K sorted arrays/lists and want to merge them. Approach: push the first element of each list into a min-heap as (value, list_index, element_index). Each time you pop the min, push the next element from that list. Time: O(n log k) where n is total elements. Key problems: Merge K Sorted Lists (LC 23) — most asked at FAANG. Smallest Range Covering Elements from K Lists (LC 632) — hard, same pattern.
Pattern 3: Two heaps (median)
Find the median of a stream or partition an array at the median. Approach: maintain a max-heap for the lower half and a min-heap for the upper half, keeping their sizes within 1 of each other. Median = average of the two tops (even count) or top of the larger heap (odd count). Key problems: Find Median from Data Stream (LC 295) — appears frequently at Google and Stripe. Sliding Window Median (LC 480) — hard.
Pattern 4: Scheduling and intervals with heaps
Process events in order of some priority. Meeting Rooms II (LC 253): use a min-heap of end times — sort meetings by start time, for each meeting check if the earliest-ending meeting has finished. Task Scheduler (LC 621): use a max-heap of task frequencies — greedily pick the most frequent available task. IPO (LC 502): two heaps for capital and profit. Key insight: heaps excel when you need to repeatedly extract the min/max of a dynamically changing set.
The lazy deletion trick
Sometimes you need to remove arbitrary elements from a heap (e.g., a sliding window heap). Python's heapq does not support arbitrary deletion. The solution: lazy deletion — instead of removing elements, mark them as deleted in a hash set. When you pop from the heap, skip any element that is in the deleted set. This is used in Sliding Window Median and some hard scheduling problems. Time complexity is unchanged — still O(log n) per operation amortized.