Heap and Priority Queue Cheat Sheet: Every Interview Fact, One Place

The heap problem is never whether you know heaps. It's whether you can remember which direction Java's comparator goes when you're ten minutes into a 45-minute interview and your brain has quietly decided to stop helping.

This is the reference you scan the morning of. Complexities, array index formulas, syntax for the four main languages, the five patterns that cover 90% of heap problems, and the three gotchas that quietly fail good candidates. No fluff. Scroll to your language if you need it fast.

Six Numbers Worth Having Cold

Build heap from an array is O(n), not O(n log n). That one surprises interviewers who haven't thought about it recently. Every other operation is logarithmic.

Operation	Time	Notes
Insert (push)	O(log n)	Sift up
Extract min/max (pop)	O(log n)	Sift down
Peek min/max	O(1)	Root is always the answer
Build heap from array	O(n)	Floyd's algorithm, not n insertions
Arbitrary element lookup	O(n)	Heaps don't support this
Delete arbitrary element	O(n)	Find it first, then O(log n) to fix
Space	O(n)	One array, no pointers

The O(n) build is worth understanding, not just memorizing. Floyd's algorithm starts from the middle of the array and sifts down, so most nodes are near the leaves and do almost no work. The math works out to O(n). See the heapify deep dive for the full proof.

The Array Is the Tree

A heap stores a complete binary tree in a flat array. No pointers. Just index arithmetic.

Parent of i:      (i - 1) // 2
Left child of i:  2 * i + 1
Right child of i: 2 * i + 2

A min-heap binary tree and its flat array representation with index labels showing parent-child relationships

For a min-heap, arr[parent] <= arr[child] always holds. The root (arr[0]) is the global minimum. For a max-heap, flip the inequality. Nothing else changes.

The heap property only guarantees the root. The second-smallest element can be at index 1 or index 2, and there's no easy way to tell which without popping. This is why heaps are terrible for sorted traversal but perfect for "just give me the next minimum" access patterns.

What Each Language Gave You (They Did Not Agree)

Python's heapq module is a min-heap. That's it. No class, no object, just functions operating on a plain list.

import heapq

h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
heapq.heappush(h, 2)

heapq.heappop(h)   # 1
h[0]               # peek: 2 (no removal)

# Build from existing list in O(n)
nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)

# Top-K utilities
heapq.nsmallest(3, nums)  # [1, 1, 3]
heapq.nlargest(3, nums)   # [5, 4, 3]

For a max-heap in Python, negate the values. Python's solution to not having a max-heap is to lie to the heap. Push -x, pop and negate the result. It works.

heapq.heappush(h, -5)
max_val = -heapq.heappop(h)  # 5

For tuples, Python compares element by element. (priority, item) is the standard pattern for breaking ties or attaching metadata:

heapq.heappush(h, (1, "task_a"))
heapq.heappush(h, (1, "task_b"))
priority, task = heapq.heappop(h)

See the Python docs for edge cases with equal priorities.

Five Patterns That Cover 90% of Heap Problems

1. Top-K Elements

Maintain a min-heap of size K while scanning. When the heap exceeds K, pop. The heap holds the K largest elements seen so far, and the root is the K-th largest.

def top_k(nums, k):
    h = []
    for n in nums:
        heapq.heappush(h, n)
        if len(h) > k:
            heapq.heappop(h)
    return list(h)

Time: O(n log k). Space: O(k). This beats O(n log n) sort when k is small. The Top-K pattern post has the full analysis.

2. Merge K Sorted Lists

Push the first element of each list into the heap as (value, list_index, element_index). On each pop, push the next element from the same list.

def merge_k_lists(lists):
    h = [(lists[i][0], i, 0) for i in range(len(lists)) if lists[i]]
    heapq.heapify(h)
    result = []
    while h:
        val, li, ei = heapq.heappop(h)
        result.append(val)
        if ei + 1 < len(lists[li]):
            heapq.heappush(h, (lists[li][ei + 1], li, ei + 1))
    return result

Time: O(n log k) where n is total elements. This is LeetCode 23.

3. Median from Stream

Two heaps: a max-heap for the lower half, a min-heap for the upper half. Keep them balanced (sizes differ by at most 1). The median is either the top of the larger heap or the average of both tops.

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negate values)
        self.hi = []  # min-heap

    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

This is LeetCode 295. It's the canonical two-heap problem and shows up often at mid-to-senior-level interviews.

4. Dijkstra's Algorithm

The heap drives the greedy selection: always relax the shortest-known-distance node first.

def dijkstra(graph, src):
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    h = [(0, src)]
    while h:
        d, u = heapq.heappop(h)
        if d > dist[u]:
            continue  # stale entry, skip
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(h, (dist[v], v))
    return dist

The if d > dist[u]: continue line is lazy deletion, which the next section explains.

5. K-th Largest / Smallest

Same structure as Top-K but you return the root after K insertions. For K-th largest, use a min-heap of size K. For K-th smallest, use a max-heap. For a full comparison of heap vs sorting for these problems, the decision comes down to whether K is small relative to n.

Three Gotchas That Quietly Derail Good Candidates

First: C++ defaults to max-heap; Python and Java default to min-heap. If you switch languages mid-prep, verify this before writing a single line. Correct logic in the wrong direction produces silent wrong answers. No runtime error. No warning. Just wrong.

Second: build heap is O(n), n insertions is O(n log n). When you need to heapify a static array, use the language's built-in heapify or Init. Both are correct; one is just slower, and interviewers notice when you explain the complexity.

Third: heaps don't support O(log n) updates to arbitrary elements. When Dijkstra finds a shorter path, you can't cheaply update the old heap entry. The standard fix is lazy deletion: push a new (new_dist, node) tuple and skip stale entries on pop with if d > dist[u]: continue. The heap grows larger than strictly necessary, but the implementation stays simple and the asymptotic complexity doesn't change for sparse graphs.

The Night Before: Do This One Thing

Talk through at least one of these patterns out loud. Not to review the code. To practice narrating the invariant. "I'm maintaining a min-heap of size K. When it exceeds K, I pop, which discards the smallest. So what remains is the K largest." That sentence, spoken clearly under pressure, is what separates a strong hire signal from a shrug.

SpaceComplexity runs voice-based DSA mock interviews where you practice exactly this: narrate the approach, state the invariant, explain the complexity. You get rubric-based feedback on whether your explanation would land with a real interviewer. Worth a run before the real thing.