Heaps and Priority Queues: An Interview Playbook

Reach for a heap when the problem keeps asking for the best of a changing set: the smallest, the largest, the closest, the soonest.

What a heap guarantees

A binary heap is a tree stored in a plain array, with the children of index i at 2i + 1 and 2i + 2. In a min-heap every parent is no larger than its children, which puts the smallest item at index 0 and promises little else. Pushing 5, 1, 9, and 3 into Python's heapq leaves the list as [1, 3, 9, 5], so a printed heap is not sorted. Push and pop each walk one path of a tree about log n levels tall. Peeking at the root is O(1), and building a heap from an unsorted array with heapify takes only O(n), a common talking point.

Top K and threshold maintenance

To find the k largest items, keep a min-heap of size k. That sounds backwards, but the item to evict when a bigger one arrives is the smallest of your current top k, which a min-heap keeps at the root.

import heapq

def top_k_largest(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # pop the root, push x
    return sorted(heap, reverse=True)

With k = 3 and [5, 1, 9, 3, 7, 8], the heap starts as 1, 5, and 9. Then 3 replaces 1, 7 replaces 3, and 8 replaces 5, which leaves 7, 8, and 9. Each item costs at most O(log k), so the whole pass is O(n log k). Top K frequent elements runs the same loop on counts from a hash map, and K closest points is the mirror image, a max-heap on distance that evicts the farthest point. When k is close to n, sorting is just as fast and simpler to explain.

Running median with two heaps

The median of a stream needs two heaps, a max-heap for the smaller half and a min-heap for the larger half. After every insert, everything in the lower half is at most everything in the upper half, and the lower half is the same size as the upper half or one item bigger.

import heapq

class MedianFinder:
    def __init__(self):
        self.lower = []  # max-heap of the smaller half, stored negated
        self.upper = []  # min-heap of the larger half

    def add(self, x):
        heapq.heappush(self.lower, -x)
        heapq.heappush(self.upper, -heapq.heappop(self.lower))
        if len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))

    def median(self):
        if len(self.lower) > len(self.upper):
            return -self.lower[0]
        return (-self.lower[0] + self.upper[0]) / 2

Every new number enters the lower half, which then hands its largest item up, so the halves stay in order without a comparison of your own. Adding 5, 15, 1, and 3 gives medians of 5, 10, 5, and 4, at O(log n) per insert and O(1) per median.

Merge and schedule by time

To merge k sorted lists, keep each list's smallest unused item in the heap, pop the smallest, and push the next item from the same list. The heap never holds more than k entries, so merging N items costs O(N log k). The meeting rooms problem works the same way, with meetings sorted by start time and a min-heap of end times whose root is the next room to free up.

Dijkstra's shortest path algorithm is the same loop with distance as the priority, for edges with different costs where plain BFS fails.

import heapq

def dijkstra(graph, source):
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue  # stale entry, a shorter path was already found
        for nxt, weight in graph[node]:
            nd = d + weight
            if nd < dist.get(nxt, float("inf")):
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))
    return dist

A heap cannot cheaply lower the priority of an item it already holds, so the code pushes the node again and skips the old entry when it comes out. Without that skip, the answer is still right but slower. Dijkstra also assumes that no edge has a negative weight.

Python, Java, and C++

Python's heapq works on a plain list and always keeps a min-heap, with heap[0] as the peek. For a max-heap, push negated numbers, as the median code does. Tuples compare field by field, so a tie on the priority falls through to comparing the items, and a dict or an object with no ordering raises a TypeError. A counter from itertools.count() placed between the priority and the item breaks those ties.

Java's PriorityQueue is also a min-heap by default, and poll() returns null on an empty queue.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> alsoMax = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

Avoid a comparator that subtracts, such as b - a, because it overflows when two values are more than about two billion apart and puts the wrong item on top.

C++'s std::priority_queue is the opposite, a max-heap by default.

std::priority_queue<int> maxHeap;  // largest on top by default
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

minHeap.push(5);
minHeap.push(1);
int smallest = minHeap.top();  // 1, read it first
minHeap.pop();                 // pop() returns nothing

A custom comparator returns true when its first argument should come out later, which is why std::greater gives a min-heap.

Pattern recognition drill

When you read a problem, ask yourself two questions.

1. Is there a repeated "pick the best next" step?
2. Can I bound the heap size to K or to the frontier of a graph search?

If both answers lean yes, sketch the heap before you reach for sorting everything. Phrases like k largest, kth smallest, k closest, median of a stream, merge k sorted, and cheapest route usually point to a heap. For the best item inside a sliding window, the deque in the sliding window guide does the job in O(n).

To make these two questions a habit, work a few heap problems through the practice routine in LeetCode interview tips.