PATTERN 11 OF 22

Heaps / Priority Queues

Use heaps (priority queues) to efficiently find and maintain the smallest or largest elements. Master the size-k heap pattern for top-k problems, the two-heap pattern for medians, and heap-based k-way merge for combining sorted sequences.

Time: O(n log k) for top-k, O(n log n) for full heap sort

Space: O(k) for top-k, O(n) for full heap

Learn & Reference

Understanding the Pattern

Heaps / Priority Queues Pattern

A heap (or priority queue) is a data structure that gives you instant access to the minimum (min-heap) or maximum (max-heap) element, with O(log n) insertion and removal. Under the hood it is a complete binary tree stored in an array, but in interviews you treat it as a black box: push items in, pop the extreme item out.

Core Concept

A min-heap always gives you the smallest element. A max-heap always gives you the largest. The key insight for interviews: when you need to repeatedly find the smallest or largest element from a changing collection, a heap is almost always the right tool.

Min-Heap (conceptual):
       1
      / \
     3   2
    / \
   7   4

peek() = 1  (always the minimum)
pop()  = 1  (removes min, heap restructures in O(log n))
push(0)     (inserts, bubbles up in O(log n))

Key Techniques

1. The Size-K Heap (Top-K Pattern)

This is THE heap interview pattern. To find the k largest elements, maintain a min-heap of size k. As you scan elements:

If the heap has fewer than k items, push the element
If the element is larger than the heap's minimum, pop the min and push the new element
Skip otherwise

After processing all elements, the heap contains exactly the k largest. The top of the min-heap is the kth largest.

Find 3 largest from [4, 1, 7, 3, 8, 5]:

Process 4: heap = [4]           (size < 3, push)
Process 1: heap = [1, 4]       (size < 3, push)
Process 7: heap = [1, 4, 7]    (size = 3, push)
Process 3: heap = [3, 4, 7]    (3 > 1, replace min)
Process 8: heap = [4, 7, 8]    (8 > 3, replace min)
Process 5: heap = [5, 7, 8]    (5 > 4, replace min)

Result: top 3 are [5, 7, 8], kth largest = 5

Why min-heap for k largest? Because the min-heap's top is the gatekeeper — it is the smallest of the k largest seen so far. Any element smaller than it cannot be in the top k and is skipped.

2. The Two-Heap Pattern (Dual-Heap)

For maintaining a running median, use two heaps:

A max-heap for the lower half of numbers (gives you the largest of the small numbers)
A min-heap for the upper half (gives you the smallest of the large numbers)

Keep them balanced: the max-heap may have at most one more element than the min-heap. The median is either the max-heap's top (odd count) or the average of both tops (even count).

Stream: 5, 2, 8, 1

After 5:  maxHeap=[5]       minHeap=[]         median = 5
After 2:  maxHeap=[2]       minHeap=[5]        median = (2+5)/2 = 3.5
After 8:  maxHeap=[2]       minHeap=[5,8]      → rebalance →
          maxHeap=[2,5]     minHeap=[8]        median = 5... wait
          Actually: maxHeap=[5,2] minHeap=[8]  median = 5
After 1:  maxHeap=[2,1]     minHeap=[5,8]      median = (2+5)/2 = 3.5

3. K-Way Merge with Heap

To merge k sorted lists, push the first element of each list into a min-heap (along with its list index). Repeatedly pop the minimum, add it to the result, and push the next element from that same list. The heap always has at most k elements.

4. Greedy Scheduling with Heap

Some problems (like task scheduling) use a max-heap to greedily pick the highest-priority item at each step. After processing, items may re-enter the heap (possibly with a cooldown delay). The heap ensures you always make the optimal greedy choice.

5. When to Use a Heap vs. Sorting

Need all elements sorted: just sort — O(n log n) time, simpler code
Need only top k of n elements: heap — O(n log k) time, better when k << n
Need to repeatedly insert and extract extremes: heap — O(log n) per operation
Need the median of a stream: two-heap — O(log n) per insertion, O(1) median query
Merging k sorted sequences: heap — O(N log k) where N is total elements

Common Mistakes

Using a max-heap when you need a min-heap (or vice versa): To find the k largest elements, use a min-heap of size k. The min-heap's top is the kth largest. Using a max-heap of size k gives you the k smallest instead. Think about which element the heap's top should represent
Forgetting to limit heap size: The top-k pattern only works if you maintain the heap at size k. If you push all n elements without popping, you have a full heap of size n — equivalent to sorting with extra overhead
Not handling tie-breaking in Python heapq: Python's heapq compares tuples element by element. If the first element ties, it compares the second. If you push (priority, object) and objects are not comparable, you get a TypeError. Always include a tie-breaking index: (priority, index, object)
Mutating heap elements after insertion: A heap maintains its invariant based on values at insertion time. If you change an element's priority after pushing it, the heap order breaks silently. Either remove and re-insert, or use lazy deletion (mark as invalid, skip when popped)
Forgetting that JavaScript has no built-in heap: Unlike Python (heapq), Java (PriorityQueue), and Go (container/heap), JavaScript and TypeScript have no native heap. In interviews, you either implement a simple one or use a provided helper. Plan for this in your practice

When to Use

Find the kth largest / smallest element

Top k or k most frequent or k closest

Continuously find the median or running median

Merge k sorted arrays, lists, or streams

Schedule tasks with priorities or cooldowns

Any problem where you repeatedly need the min or max from a dynamic collection

Keywords: kth, top-k, priority, largest, smallest, median, merge k, schedule, frequent, closest

Template

1# --- Top-K Template: Find kth largest using min-heap of size k ---
2import heapq
3
4def find_kth_largest(nums, k):
5    heap = []
6    for num in nums:
7        heapq.heappush(heap, num)
8        if len(heap) > k:
9            heapq.heappop(heap)  # evict smallest
10    return heap[0]  # kth largest is the min of the top-k
11
12# Example: find_kth_largest([3, 2, 1, 5, 6, 4], 2) → 5

{ }

Syntax Reference

1# --- Python: heapq (min-heap) ---
2import heapq
3
4heap = []
5
6# Push onto heap
7heapq.heappush(heap, val)          # O(log n)
8
9# Pop minimum
10smallest = heapq.heappop(heap)     # O(log n)
11
12# Peek at minimum (without removing)
13smallest = heap[0]                  # O(1)
14
15# Heap size
16size = len(heap)
17
18# Build heap from list (in-place)
19heapq.heapify(nums)                # O(n)
20
21# Push and pop in one operation
22result = heapq.heappushpop(heap, val)  # More efficient than push + pop
23
24# --- Max-Heap Trick ---
25# Python only has min-heap. Negate values for max-heap:
26heapq.heappush(heap, -val)         # push negated
27largest = -heapq.heappop(heap)     # pop and negate back
28
29# --- Tuple Comparison ---
30# heapq compares tuples element-by-element
31heapq.heappush(heap, (priority, index, item))  # index breaks ties

📋

Common Recipes

1# --- Top-K Pattern (k largest elements) ---
2import heapq
3
4def top_k_largest(nums, k):
5    heap = []
6    for num in nums:
7        heapq.heappush(heap, num)
8        if len(heap) > k:
9            heapq.heappop(heap)  # remove smallest
10    return heap  # contains k largest, heap[0] is kth largest
11
12# --- Two-Heap Median ---
13class MedianFinder:
14    def __init__(self):
15        self.lo = []   # max-heap (negated) for lower half
16        self.hi = []   # min-heap for upper half
17
18    def add_num(self, num):
19        heapq.heappush(self.lo, -num)
20        heapq.heappush(self.hi, -heapq.heappop(self.lo))
21        if len(self.hi) > len(self.lo):
22            heapq.heappush(self.lo, -heapq.heappop(self.hi))
23
24    def find_median(self):
25        if len(self.lo) > len(self.hi):
26            return -self.lo[0]
27        return (-self.lo[0] + self.hi[0]) / 2
28
29# --- K-Way Merge ---
30def merge_k_sorted(lists):
31    heap = []
32    for i, lst in enumerate(lists):
33        if lst:
34            heapq.heappush(heap, (lst[0], i, 0))
35    result = []
36    while heap:
37        val, list_idx, elem_idx = heapq.heappop(heap)
38        result.append(val)
39        if elem_idx + 1 < len(lists[list_idx]):
40            next_val = lists[list_idx][elem_idx + 1]
41            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
42    return result
43
44# --- Greedy Scheduling ---
45# Use max-heap to always pick highest-frequency task
46# See Task Scheduler problem for full implementation

O(n)

Complexity

Operation	Time	Space
Heap push	O(log n)	O(1)
Heap pop (extract min/max)	O(log n)	O(1)
Heap peek	O(1)	O(1)
Build heap (heapify)	O(n)	O(1)
Top-k of n elements	O(n log k)	O(k)
Two-heap median (per insert)	O(log n)	O(n)
K-way merge (N total elements)	O(N log k)	O(k)

Watch Out

✗Using a max-heap when you need a min-heap (or vice versa): To find the k *largest* elements, use a *min*-heap of size k. The min-heap's top is the kth largest. Using a max-heap of size k gives you the k *smallest* instead. Think about which element the heap's top should represent
✗Forgetting to limit heap size: The top-k pattern only works if you maintain the heap at size k. If you push all n elements without popping, you have a full heap of size n — equivalent to sorting with extra overhead
✗Not handling tie-breaking in Python heapq: Python's heapq compares tuples element by element. If the first element ties, it compares the second. If you push `(priority, object)` and objects are not comparable, you get a TypeError. Always include a tie-breaking index: `(priority, index, object)`
✗Mutating heap elements after insertion: A heap maintains its invariant based on values at insertion time. If you change an element's priority after pushing it, the heap order breaks silently. Either remove and re-insert, or use lazy deletion (mark as invalid, skip when popped)
✗Forgetting that JavaScript has no built-in heap: Unlike Python (`heapq`), Java (`PriorityQueue`), and Go (`container/heap`), JavaScript and TypeScript have no native heap. In interviews, you either implement a simple one or use a provided helper. Plan for this in your practice

PRACTICE PROBLEMS

Trees (BFS)

Graphs (BFS/DFS)