Heaps and Priority Queues — Master Recap and Interview Cheatsheet

Why a Master Recap Matters#

If you have walked through the entire Heaps section, you have seen how a single data structure — the binary heap — powers an enormous range of interview questions. Top-K, dynamic median, scheduling, merging streams, graph traversal, even meeting rooms and CPU task scheduling all reduce to "what is the smallest or largest right now?". This master recap distills the section into seven patterns, a complexity cheatsheet, and a full problem index so you can revise the entire heap chapter in under thirty minutes before a FAANG interview.

The Mental Model in One Paragraph#

A binary heap is a complete binary tree stored in an array where every parent is at least as small (min-heap) or large (max-heap) as its children. That single invariant gives you O(log n) push and pop and O(1) peek. Whenever an interview problem repeatedly asks "what is the current min or max of an evolving set?", a heap is almost always the right answer. The art is recognising the question — usually disguised as "k closest", "kth largest", "median so far", "merge k sorted things", or "do this expensive task next".

The 7 Core Heap Patterns#

Pattern 1 — Top K with a Fixed-Size Heap#

Use a heap of size k to keep only the k best elements seen so far. For "k largest" use a min-heap so the smallest of the top-k is at the root and easy to evict. For "k smallest" use a max-heap.

import heapq
 
def top_k_largest(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap  # heap[0] is the kth largest

// Use a min-heap class; size capped at k
function topKLargest(nums, k) {
    const heap = new MinHeap();
    for (const n of nums) {
        heap.push(n);
        if (heap.size() > k) heap.pop();
    }
    return heap.toArray();
}

Time O(n log k), space O(k). Examples: Kth Largest Element, K Closest Points, Top K Frequent.

Pattern 2 — Two Heaps for Dynamic Median#

Maintain a max-heap of the lower half and a min-heap of the upper half, kept balanced within one element. Median is either the top of the larger heap or the average of both tops.

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negated)
        self.hi = []  # min-heap
 
    def addNum(self, num):
        heapq.heappush(self.lo, -heapq.heappushpop(self.hi, num))
        if len(self.lo) > len(self.hi):
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
 
    def findMedian(self):
        if len(self.hi) > len(self.lo):
            return self.hi[0]
        return (self.hi[0] - self.lo[0]) / 2

Time O(log n) per add, O(1) per query. Examples: Find Median from Stream, IPO, Sliding Window Median.

Pattern 3 — Merge K Sorted Sources#

Push the head of each list, pop the smallest, push the next from that list. Works for arrays, linked lists, generators — anything ordered.

def merge_k_sorted(lists):
    heap = []
    for i, l in enumerate(lists):
        if l:
            heapq.heappush(heap, (l[0], i, 0))
    out = []
    while heap:
        val, i, j = heapq.heappop(heap)
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j+1], i, j+1))
    return out

Time O(N log k) where N is total elements. Examples: Merge K Sorted Lists, Smallest Range, Find K Pairs.

Pattern 4 — Greedy Scheduling with a Heap#

Sort events by some key (start time, deadline, profit) and use a heap to pick the best available option at each step.

def task_scheduler(tasks):
    # tasks = [(deadline, duration), ...]
    tasks.sort()
    heap = []
    time = 0
    for d, t in tasks:
        heapq.heappush(heap, -t)
        time += t
        if time > d:
            time += heapq.heappop(heap)  # drop largest
    return len(heap)

Examples: Course Schedule III, Meeting Rooms II, Task Scheduler, Reorganize String, IPO.

Pattern 5 — Heap as a Graph Frontier (Dijkstra Style)#

Push neighbours with cumulative cost, always expand the cheapest. Works for shortest path, min-cost paths, swim in rising water, and trapping rain water II.

def dijkstra(graph, src):
    dist = {src: 0}
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')):
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Examples: Network Delay, Path with Min Effort, Swim in Rising Water, Trapping Rain Water II.

Pattern 6 — Lazy Deletion#

When you cannot remove arbitrary elements from a heap, mark them invalid and skip them only when they reach the top.

def kth_largest_with_remove(nums, k):
    heap = []
    invalid = collections.Counter()
    for n in nums:
        heapq.heappush(heap, -n)
    def top():
        while heap and invalid[-heap[0]] > 0:
            invalid[-heap[0]] -= 1
            heapq.heappop(heap)
        return -heap[0]
    return top()

Examples: Stock Price Fluctuation, Design Twitter, Process Tasks Servers.

Pattern 7 — Heap with Indexed Tuples#

When ties matter, push tuples like (priority, index, payload). Python compares tuples lexicographically, giving you stable ordering for free.

heapq.heappush(heap, (freq, -ord(char), char))

Examples: Sort Characters by Frequency, Top K Frequent Words, Reorganize String.

Complexity Cheatsheet#

When NOT to Use a Heap#

• You need range queries — use a segment tree or sorted set.
• You need ordered iteration — use a BST or sorted container.
• You need O(1) decrease-key — use a Fibonacci heap or indexed structure.
• The data fits in memory and is static — sort once, then answer in O(1).

FAANG-Style Problem Index (46 Problems)#

Interview Day Checklist#

• Recognise top-K, median, merging, scheduling, and graph-frontier patterns within the first minute.
• State the heap invariant before coding to anchor the interviewer.
• Prefer Python heapq with negation for max-heaps over a custom class.
• Always discuss lazy deletion if the problem allows arbitrary updates.
• Mention quickselect as the alternative for the kth-largest pattern.
• Know the difference between heapify (O(n)) and n pushes (O(n log n)).

Common Mistakes Across the Section#

• Using a max-heap when a min-heap would shrink to size k more naturally.
• Forgetting to break ties with an index, causing comparison errors on tuples.
• Removing arbitrary elements in O(n) instead of using lazy deletion.
• Confusing the kth largest (min-heap of size k) with the kth smallest (max-heap of size k).
• Failing to balance the two heaps after every insertion in the median pattern.

Follow-Up Questions to Try#

• Implement a d-ary heap and benchmark it against a binary heap.
• Build an indexed priority queue with O(log n) decrease-key.
• Solve k-way merge with a tournament tree instead of a heap.
• Prove the O(n) build-heap bound using the geometric sum of heights.
• Compare Fibonacci heaps to binary heaps for Dijkstra on dense graphs.

Key Takeaways#

• Seven heap patterns cover virtually every priority-queue interview question: Top-K, Two Heaps, Merge K, Greedy Scheduling, Dijkstra Frontier, Lazy Deletion, and Indexed Tuples.
• A min-heap of size k yields the k largest elements in O(n log k) time and O(k) space — the canonical Top-K solution.
• Two heaps (max-heap of lower half, min-heap of upper half) maintain a streaming median in O(log n) per insert.
• Lazy deletion lets you support arbitrary updates without paying the O(n) arbitrary-delete cost of a binary heap.
• Tuple comparison gives you stable tie-breaking for free; always include an index when payloads are not naturally comparable.
• Heaps power Dijkstra, Prim, Huffman coding, and many scheduling algorithms — recognising the frontier pattern unlocks graph problems too.
• Build-heap is O(n) but n successive pushes are O(n log n); use heapify when you have all data upfront.