Heap / Priority Queue
- Explain why a min-heap finds the k largest elements while a max-heap would require storing all n elements
- Design a two-heap median solution by identifying which heap property gives O(1) access to the boundary between halves
- Recognize when stale-entry skipping is needed and why outdated heap entries do not affect correctness if checked on pop
- Distinguish when a heap is the right tool from when sort or quickselect is simpler
A heap maintains one property in constant time: which candidate currently has the highest or lowest priority. Problems that need repeated access to the best available candidate as data changes are heap problems. Problems that need one answer from static data are usually not.
Heap Reference
| Operation | Time | Why |
|---|---|---|
| Insert | O(log n) | Bubble up |
| Extract Min/Max | O(log n) | Bubble down |
| Peek | O(1) | Return root |
| Heapify | O(n) | Bottom-up build |
| Search | O(n) | No order guarantee |
What Heaps Actually Do
Finding the top k elements from a stream of n values illustrates what a heap is built for. Start with the brute force approaches and see where each one fails.
The Brute Force Progression
Attempt 1: Sort after each insertion. Collect all elements, sort them, take the top k. Each new element triggers a full resort: O(n log n) per element, O(n² log n) total. This is correct but impractical for large n.
Attempt 2: Maintain a sorted array with binary search insert. Binary search finds the insertion point in O(log n), but shifting elements to make room costs O(n). Still O(n) per element.
Attempt 3: Store everything in a max heap, pop k times at the end. Building the heap is O(n) via heapify, then popping k times costs O(k log n), giving O(n + k log n) total. For very small k, this is near-optimal in time. But it uses O(n) space and requires all elements to be available upfront.
The bounded heap approach: maintain exactly k candidates in a min heap. For each new element, compare to the root in O(1). If the element is larger, push and pop in O(log k). If smaller, discard. After all n elements: O(n log k) time, O(k) space. This works on streaming data where you cannot see all n elements upfront.
When to Use a Heap
The key question is: what property must be maintained repeatedly as data changes? Four signals map directly to heap sub-patterns:
- Repeated access to the min or max from changing data: standard heap
- kth element as data streams: bounded heap of size k
- Median of stream: two heaps
- Global minimum across k sorted sources: k-way merge heap
| Problem Type | What Changes | What Is Needed Repeatedly |
|---|---|---|
| kth largest in stream | New elements arrive | The kth largest so far (min of top k) |
| median in stream | New elements arrive | The middle value |
| merge k sorted lists | Iteration through lists | The global minimum across all k lists |
| task scheduler | Tasks complete | The task with highest remaining count |
How Heap Order Works
A heap is a complete binary tree stored as an array where every parent is smaller than its children (min heap) or larger (max heap). "Complete" means every level is full except possibly the last, which fills left to right. This guarantees height ⌊log₂ n⌋, capping every insertion and deletion at O(log n).
Completeness enables array storage without pointers. The parent of node at index i lives at ⌊(i-1)/2⌋, the left child at 2i+1, the right child at 2i+2. No linked nodes, no null checks, no wasted array slots. This is why heaps outperform balanced BSTs for pure min/max access: the data lives in a contiguous array with smaller constant factors.
| Operation | Complexity | What It Does |
|---|---|---|
| peek(heap[0]) | O(1) | Look at the minimum without removing it |
| heappush(heap, x) | O(log n) | Add element x, maintaining heap property |
| heappop(heap) | O(log n) | Remove and return the minimum |
Python's heapq is a min heap. The smallest element is always at the root.
Language note: Python heapq: min-heap. Java PriorityQueue: min-heap. C++ priority_queue: max-heap (opposite of Python). JavaScript: no built-in heap.
Push, Pop, and Heapify
These operations are rarely implemented in interviews, but the mechanics explain where O(log n) comes from and where edge cases hide.
Push (Bubble Up)
Insertion places the new element at the end of the array (maintaining completeness), then bubbles it up: compare with parent, swap if smaller (min heap), repeat until the heap property is restored. The worst case traverses from leaf to root, a path whose length is exactly the tree height. Because the complete binary tree property guarantees height ⌊log₂ n⌋, push is O(log n).
Heap Insert (Bubble Up)
Step 1 of 6 · Valid min heap where every parent is less than or equal to its children. Root (1) is the minimum. Now insert 2.
Pop (Bubble Down)
Extraction swaps the root with the last element, removes the last element, then bubbles the new root down: compare with children, swap with the smaller child (min heap), repeat until the heap property is restored. The worst case again traverses the full height of the tree: O(log n).
Heap Extract (Bubble Down)
Step 1 of 6 · Goal is to remove and return the minimum which is the root. The root is always the min in a min heap.
Heapify: O(n), Not O(n log n)
Building a heap from an existing array costs O(n), not O(n log n), because most nodes sit near the bottom where very little work is needed.
Bottom-Up Heapify (O(n))
Step 1 of 7 · Unsorted array as a complete binary tree. Goal: transform into a valid min heap using bottom-up heapify.
Use heapify when all elements are available upfront. Use repeated push when elements arrive one at a time.
First Walkthrough: Top K in a Stream
Walk through nums = [4, 1, 7, 3, 8, 5], k = 3 step by step to see exactly what the bounded heap does at each element.
| Element | Action | Heap After | What Became Known |
|---|---|---|---|
| 4 | Push. Size 1, below k. | [4] | No threshold yet. Keep everything. |
| 1 | Push. Size 2, below k. | [1, 4] | No threshold yet. Keep everything. |
| 7 | Push. Size 3, at k. Root = 1. | [1, 4, 7] | Threshold established. Root is the weakest of our 3 candidates. |
| 3 | 3 > root(1). Push then pop 1. Size stays 3. | [3, 4, 7] | 1 is eliminated. 3 is a stronger candidate. The threshold rises to 3. |
| 8 | 8 > root(3). Push then pop 3. Size stays 3. | [4, 7, 8] | 3 is eliminated. 8 enters. The threshold rises to 4. |
| 5 | 5 > root(4). Push then pop 4. Size stays 3. | [5, 7, 8] | 4 is eliminated. 5 enters. Final top 3: {5, 7, 8}. |
Each element either evicts the weakest current candidate (push and pop), strengthens the threshold, or gets discarded because it cannot beat the current threshold. The heap root is always the element one improvement away from being eliminated.
Top K Largest (Min-Heap of Size K)
Step 1 of 9 · Goal is to find the top 3 largest. The key insight is to use a MIN heap. The min becomes our threshold to beat.
Notice that when an element is smaller than the root, the heap does nothing in O(1). The root proves that element has no place in the top k without requiring any search.
Heap Templates
Four templates cover most heap problems. Each maintains a different invariant about which candidate sits at the root.
Template 1: Top K
A min heap of size k keeps the k largest by surfacing the minimum at the root. When a new element arrives, compare it to the root. If larger, push it and pop the old root. If smaller or equal, skip it. This runs in O(n log k) time and O(k) space. An unbounded heap would store all n elements and require k pops at the end, using O(n) space without the streaming benefit.
With n = 10 million and k = 10, the bounded heap needs about 3.3 comparisons per element instead of 23. The smaller k is relative to n, the larger the advantage over sorting.
Top K Smallest (Inverted Logic)
Use a max heap of size k instead. Python only has min heap, so negate values.
Template 2: K-Way Merge
Merging k sorted lists requires repeatedly finding the global minimum across all k list heads. A naive approach compares all k heads each time, costing O(k) per element and O(nk) total. With a min heap holding one element from each list, finding the global minimum costs O(log k) per step.
Pop the minimum, append to result, then push the next element from that same list. The heap always contains at most k elements (one per active list), and the root is always the smallest remaining element across all sources.
To know which list an element came from, store tuples: (value, list_index, element_index). Python compares tuples left-to-right, so the heap orders by value. The list_index serves as a tiebreaker when two values are equal, preventing Python from attempting to compare non-comparable objects at the next tuple position.
K-Way Merge
Step 1 of 11 · Goal is to merge k sorted lists into one. Naive approach compares all k heads each step which is O(k). With a heap it is O(log k).
The heap holds at most k elements throughout, one per active list. When a list is exhausted, its slot in the heap disappears. Time is O(N log k) where N is the total number of elements across all lists. Space is O(k).
Template 3: Two Heaps for Running Median
The median is the middle value of sorted data. Full sorted order is unnecessary. Only the largest value in the smaller half and the smallest value in the larger half are needed. These two values bracket the median.
Use a max heap for the smaller half (gives O(1) access to its largest element) and a min heap for the larger half (gives O(1) access to its smallest element). The two roots are always adjacent to the median.
The Two Invariants and Why They Work
Invariant 1: max(small) is less than or equal to min(large). If this is violated, the largest element in the smaller half is bigger than the smallest element in the larger half, meaning elements are in the wrong halves. The fix is to move the max of small to large.
Invariant 2: sizes differ by at most 1. If one heap holds five elements and the other holds three, the root of the larger heap is not at the true median position. Balancing keeps the roots at the boundary.
With odd count, one heap has the extra element, and the median is that heap's root. With even count, the median is the average of both roots.
Two Heaps (Find Median)
Step 1 of 8 · The median lives at the boundary between smaller and larger halves. Two heaps let us access that boundary instantly.
Template 4: Scheduling
Scheduling problems like Task Scheduler involve a cooldown constraint: the same task cannot run within n time units of itself. With tasks [A, A, A, B, B, C] and cooldown 2, one valid sequence is A B C A B _ A (7 time units), where _ represents forced idle time.
The most frequent task creates the skeleton. Task A appears 3 times with cooldown 2, forcing the structure A _ _ A _ _ A (7 slots). Other tasks fill the gaps. Processing the most constrained task first minimizes wasted idle time.
The Formula Approach
The minimum time can be computed directly without simulation. The formula is:
Think of the schedule as (max_freq - 1) blocks, each of size (n + 1). Every block starts with one occurrence of the most frequent task, followed by n cooldown slots that other tasks can fill. The last block contains only tasks that share the maximum frequency. If enough diverse tasks exist to fill every gap, no idle time is needed and the answer is len(tasks).
The Simulation Approach
At each time step, the algorithm needs the task with the highest remaining count that is not on cooldown. A max heap ordered by count provides this in O(log n). After processing a task, its count is decremented and it enters a cooldown queue. When its cooldown expires, it re-enters the heap.
Task Scheduler Simulation
Step 1 of 8 · Tasks: Ax3, Bx2, Cx1 with cooldown n=2. Initialize max heap ordered by frequency count.
When This Pattern Breaks
Stale Entries and When to Skip Them
Heaps do not support efficient removal from the middle of the structure. Locating and removing a specific element costs O(n). When a heap entry becomes outdated but cannot be removed efficiently, the solution is to leave the stale entry in the heap and check its validity when it reaches the top.
In Dijkstra's algorithm, a node may be pushed to the heap multiple times as shorter paths are discovered. Each new push creates a fresh entry with a shorter distance. The older, longer-distance entry remains in the heap because finding and removing it would require scanning the entire structure. When the older entry eventually reaches the top, the algorithm checks whether its recorded distance matches the current known shortest distance for that node. If it does not match, the entry is stale and gets skipped. Only the entry that matches represents valid work.
The heap may contain multiple entries for the same node, but only the entry with the current shortest distance is ever processed. The others are skipped in O(1) when they reach the top. If most entries are stale, the heap can grow to O(n) entries for n nodes, which degrades performance compared to a structure that supports true deletion.
When a Heap Is the Wrong Tool
A heap is optimized for one operation: access to the minimum or maximum. When the problem needs something else, the heap's partial order becomes a liability.
- Need to remove an arbitrary element efficiently: a balanced BST or sorted container (like Python's sortedcontainers.SortedList) supports O(log n) arbitrary removal. A heap does not.
- One-time kth element query on static data: quickselect runs in O(n) average time. A heap costs O(n log k) and builds a persistent structure you do not need.
- Need full sorted order: a heap gives partial order. Extracting all n elements in sorted order requires n pops at O(log n) each, totaling O(n log n), which is no better than sorting directly.
- Median of a fixed array: sort once and index. Sorting costs O(n log n) but the median query is then O(1) for any number of reads.
Heap vs Sort vs Quickselect
Not every problem that mentions "largest" or "smallest" is a heap problem. The choice depends on whether data is static or streaming and whether the query is one-time or repeated.
| Question | If Yes | If No |
|---|---|---|
| Is data streaming (arriving over time)? | Heap: can process elements as they arrive | Sort or Quickselect may suffice |
| Do you need repeated access to the min or max? | Heap: O(1) peek, O(log n) update | Single query: Quickselect O(n) |
| Do you need the kth element specifically? | Bounded heap of size k: O(n log k) | If just min/max, unbounded heap works |
| Do you need both min and max simultaneously? | Two heaps: median pattern | Single heap for one end |
| Do you need full sorted order? | Sort: heap gives partial order only | Heap is cheaper if partial order suffices |
| Are values bounded integers (small range)? | Consider counting sort / bucket sort O(n) | Heap for comparison-based O(n log k) |
| Scenario | Best Choice | Why |
|---|---|---|
| Static array, single "find kth" query | Quickselect | O(n) average, no extra structure needed |
| Static array, multiple queries | Sort once | O(n log n) once, then O(1) per query |
| Stream, maintain top k as data arrives | Bounded heap of size k | O(n log k) total, O(k) space |
| Stream, maintain median | Two heaps | O(n log n) total, O(1) median access |
| Need min/max with arbitrary removal | Balanced BST or sorted container | Heap does not support efficient mid-removal |
Debugging the Heap
When a heap solution produces wrong answers, check these in order: is the heap type correct for what you need at the root? Is the heap bounded at the right size? Are you comparing the right value? Are stale entries handled?
Using a max heap to find the top k largest seems intuitive ("big values belong in a big-valued heap") but requires storing all n elements. The bounded optimization requires the opposite: the heap root must surface the weakest candidate for eviction, and the weakest among the k largest is the smallest. Hence min heap.
Python's heapq module only provides min heap operations. For max heap behavior, negate values on the way in and negate again on the way out.
The pattern is push first, then check size. Pop only when size exceeds k. Using == k pops before the kth element has a chance to compete.
Popping at == k removes an element before the next push, leaving k-1 elements temporarily. After the next push the heap returns to k, but the wrong element was evicted.
Pushing custom objects fails because Python does not know how to compare them. Use tuples (comparison_key, ...) or implement __lt__.
Always check if the heap is empty before peeking or popping.
When two elements have equal priority values, Python compares the next tuple element. If that element is a non-comparable object (ListNode, custom class), the comparison crashes with a TypeError.
Practice Problems
Top K / Kth Element
| Problem | Difficulty | Approach |
|---|---|---|
| Kth Largest Element in Array | Medium | Min heap of size k gives O(n log k). Quickselect gives O(n) average but O(n²) worst case. The heap approach is safer in interviews because worst case is guaranteed. |
| Top K Frequent Elements | Medium | Build a frequency map in O(n), then use a min heap of size k keyed by frequency. Bucket sort is also O(n) but uses more space. |
| Top K Frequent Words | Medium | Same frequency map approach, but with a lexicographic tiebreaker. When frequencies are equal, the heap must compare words alphabetically. |
| K Closest Points to Origin | Medium | Max heap of size k by distance. The max heap evicts the farthest point among the k candidates, keeping the k closest. |
K-Way Merge
| Problem | Difficulty | Approach |
|---|---|---|
| Merge K Sorted Lists | Hard | Heap of (node.val, list_index, node). The list_index tiebreaker prevents ListNode comparison crashes. Each pop yields the global minimum; push the next node from the same list. |
| Kth Smallest in Sorted Matrix | Medium | Treat each row as a sorted list. Initialize the heap with the first element from each row, then pop k times. |
| K Pairs with Smallest Sums | Medium | Heap of (sum, i, j). Start with (nums1[0]+nums2[0], 0, 0) and expand neighbors. Deduplication via a visited set prevents re-processing. |
Two Heaps
| Problem | Difficulty | Approach |
|---|---|---|
| Find Median from Data Stream | Hard | Max heap for the smaller half, min heap for the larger half. The two roots bracket the median. Balance sizes so they differ by at most 1. |
Scheduling / Greedy
| Problem | Difficulty | Approach |
|---|---|---|
| Task Scheduler | Medium | Formula approach: (max_freq - 1) * (n + 1) + count_of_max_freq. Simulation approach: max heap by remaining count with cooldown queue. |
| Reorganize String | Medium | Max heap by character frequency. Alternate the most frequent character to avoid adjacent duplicates. If the most frequent character exceeds (n+1)/2, no valid arrangement exists. |
| Maximum Number of Events | Medium | Sort events by start time. At each day, push all events that have started into a min heap keyed by end time. Pop the one ending soonest. |
Reference Templates
Compact code shapes for recovering the pattern. Each template includes one context line explaining when to reach for it.
Top K Largest
Use when you only need the best k elements and can evict the weakest candidate.
K-Way Merge
Use when several sorted sources each expose one current candidate.
Two Heaps (Running Median)
Use when the answer lives at the boundary between a lower half and upper half.
Scheduling by Priority
Use when the next item should be selected by remaining count, deadline, or priority.
Stale-Entry Skipping
Use when heap entries become outdated and should be checked when popped, not removed in place.
Pattern Recap
Top K
A bounded min heap of size k keeps only the k largest candidates. The root is the weakest survivor and serves as the eviction threshold. Each new element either beats the root (push and pop) or gets discarded (O(1) comparison).
Breaks when you use a max heap (stores all n elements, no eviction threshold) or when the pop condition uses == k instead of > k.
K-Way Merge
The heap holds exactly one entry per source list. The root is always the global minimum across all sources. Pop it, append to result, push the next element from the same list. Heap size never exceeds k.
Breaks when the source index is missing from the tuple (cannot advance the right list) or when equal-valued entries carry non-comparable objects without a tiebreaker.
Two Heaps (Running Median)
A max heap holds the smaller half, a min heap holds the larger half. The two roots bracket the median. Size balance ensures the roots are at the true middle. Always insert into the max heap first, then rebalance.
Breaks when either invariant is skipped: max(small) exceeding min(large) means elements are in the wrong half; size imbalance beyond 1 means the roots no longer represent the median.
Scheduling
The most frequent task determines the minimum frame structure. A max heap by remaining count selects the most constrained task at each step. Other tasks fill cooldown gaps. When enough diverse tasks exist to fill every gap, no idle time is needed.
The formula approach is O(n) and works for the standard problem. The simulation generalizes to variants with task dependencies or variable durations.
Rebuilding the Pattern
When a heap problem feels unclear, start with the question: what do I need repeated access to? If the answer is the minimum or maximum of a changing collection, a heap provides that in O(1) with O(log n) updates.
Then ask whether the collection is bounded. If you only need the best k candidates out of n elements, the heap should be bounded at size k. The root becomes the eviction threshold, and any element that cannot beat the root is discarded immediately. This is the difference between O(n log n) and O(n log k).
Then ask whether you need access to both ends. If the problem asks for the median, the answer sits at the boundary between two halves. One heap manages each half and gives O(1) access to the boundary value. Any insertion may temporarily violate the ordering or size invariants, and a fixed rebalancing sequence restores them.
Then ask whether you are merging multiple sorted sources. If so, the heap holds one entry per source and routes each pop back to the correct source list for the next push. The heap size is k throughout, not N.
A heap solution is recoverable from three decisions: what priority the heap tracks (min or max, by what key), what size the heap should be (bounded or unbounded), and what happens after each pop (what gets pushed next, and whether the popped entry might be stale). If you can answer those three questions, you can write the loop.
Check Your Understanding
Use these questions to check whether you can reason through the pattern without looking at the template.
Take Assessment
11 questions covering heap templates, debugging, and pattern selection.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Heaps and Priority Queues in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.