Heaps

When to reach for it

• Top k, k smallest, k most frequent, k closest.
• Repeatedly taking the next smallest item from a collection that keeps changing: merging sorted streams, scheduling by deadline, simulating events in time order.
• A running median, using two heaps that meet in the middle.
• Picking the cheapest next step in a weighted graph, as Dijkstra's algorithm does.

The core idea

A binary heap is an array arranged so every parent is no larger than its children, which keeps the minimum at index 0. Python's heapq module gives you a min-heap: heappush and heappop are O(log n), and reading heap[0] is O(1). For a max-heap, push negated values.

To keep the k largest of n items, keep a min-heap of size k: push each item and, once the heap holds more than k, pop the smallest. What remains are the k largest, and the top is the kth largest. To merge sorted streams, keep one entry per stream in the heap and always pop the smallest head, then push that stream's next item.

A Python template

import heapq

def k_closest(points, k):
    """The k points nearest the origin."""
    heap = []                                   # max-heap by distance, via negation
    for x, y in points:
        heapq.heappush(heap, (-(x * x + y * y), x, y))
        if len(heap) > k:
            heapq.heappop(heap)                 # evict the farthest of the k + 1
    return [(x, y) for _, x, y in heap]

def merge_streams(streams):
    """Yield items from several sorted streams in overall sorted order."""
    iters = [iter(s) for s in streams]
    heap = []
    for i, it in enumerate(iters):
        first = next(it, None)
        if first is not None:
            heap.append((first, i))             # i breaks ties between equal items
    heapq.heapify(heap)
    while heap:
        item, i = heapq.heappop(heap)
        yield item
        nxt = next(iters[i], None)
        if nxt is not None:
            heapq.heappush(heap, (nxt, i))

Time and space

Selecting k of n items with a heap of size k is O(n log k) time and O(k) space, better than sorting everything at O(n log n) when k is small, and it works on a stream you cannot hold in memory. Merging streams with N items in total is O(N log s) for s streams. heapify turns a list into a heap in O(n).

Common mistakes

• Heaping all n items when a heap of size k is enough.
• Forgetting that heapq is a min-heap, then wondering why the largest items get evicted.
• Pushing tuples whose later fields cannot be compared when the first fields tie; add a counter or index.
• Popping from an empty heap.
• Stating O(n log n) when the heap is bounded by k; the bound is the reason to use it.

How to explain it out loud

Explain the bounded heap in one sentence: "I keep the k best so far with the worst of them on top, so it's ready to be evicted when something better arrives." Interviewers often ask why a min-heap finds the largest items; having that sentence ready is good code defense.

Give both the time and the space, O(n log k) and O(k), and compare with sorting. Mention ties and k larger than n. If the data arrives as a stream, say that the heap never needs the whole stream at once; that is often the real reason the interviewer chose the question.