Heaps: The Core Idea

Think of a hospital emergency room. Patients arrive all day. The nurse never sorts the whole waiting room; she only needs to know, at any moment, who is the most urgent. When that patient is taken in, she needs the next most urgent. When a new patient arrives, she needs to fit them in quickly.

A heap is that nurse. It gives you the smallest (or largest) item of a changing collection in constant time, and it absorbs a new item or removes the top one in O(log n). It does this without ever keeping the collection sorted. That is the whole trick: it does less work than sorting, just enough to know the extreme.

How to recognise it

Four signals in the problem statement point to a heap.

1. "Top K", "the k-th largest", "the k closest", "the k most frequent". You want a handful of extremes out of many items. This is the clearest signal there is.
2. Data arrives over time and a statistic must be ready after each arrival. "Find the median of a stream", "return the k-th largest after every insert". Sorting on every arrival is far too slow.
3. You keep taking the current minimum or maximum from a collection that changes. Scheduling (run the task with the most work left), simulation (process the next event in time order), and Dijkstra's algorithm (visit the nearest unvisited node) all have this shape.
4. "Merge k sorted …". You repeatedly need the smallest head among k sources.

The constraints add a second signal. If n is up to 10⁵ or 10⁶ and k is small, the problem is asking for O(n log k), which is a size-k heap. If the input is a stream with no end, you cannot sort it at all.

Here is the brute force that the heap improves on. To find the k-th largest of n numbers, sort and index:

def kth_largest_by_sorting(numbers: list[int], k: int) -> int:    """Sort from largest to smallest and pick position k - 1."""    return sorted(numbers, reverse=True)[k - 1]

That is O(n log n). For a one-off query on a modest array it is a fine answer, and you should say so. It becomes the wrong answer in two situations. When k is much smaller than n, sorting arranges a million items when you needed 5: about 20 million comparisons, against about 2.3 million for a size-5 heap. And when data is a stream, you would re-sort after every arrival.

How it works

Because the tree is complete, it packs into a plain array with no gaps and no pointers. For the item at index i:

left child   = 2i + 1right child  = 2i + 2parent       = (i - 1) // 2

The array [2, 7, 4, 10, 9, 8] is this tree:

            2          <- index 0          /   \        7       4      <- indices 1, 2       / \     /     10   9   8        <- indices 3, 4, 5

Check it: index 1 (value 7) has children at 3 and 4, values 10 and 9, both larger. Index 2 (value 4) has one child at 5, value 8, larger. The property holds. Note that 7 sits before 4 in the array; siblings are unordered, and that is allowed.

Push (sift-up). Put the new item at the end of the array, then swap it with its parent while it is smaller. Insert 1 into [2, 7, 4, 10, 9, 8]:

Pop (sift-down). The root is the answer. Move the last item into the root's place (so the tree stays complete), then swap it with its smaller child while it is larger than that child. Pop from [1, 7, 2, 10, 9, 8, 4]: 1 is returned, 4 moves to the root, it swaps with the smaller child 2, then stops because its only child 8 is larger. Result: [2, 7, 4, 10, 9, 8].

Swapping with the smaller child is not a detail. Swap with the larger one and the new parent is bigger than its other child, which breaks the property at once.

The invariant. Every parent beats its children. Push and pop each repair it along one path from a leaf to the root, and that path is log₂ n long. That is why both cost O(log n), and why the root is always the extreme.

Variants

Heap problems come in four arrangements. Knowing which one you are in tells you the size of the heap and what goes into it.

The templates

Python's heapq implements a min-heap on a plain list. Everything else is built on top of that.

1import heapq23def top_k_largest(numbers: list[int], k: int) -> list[int]:4    """Return the k largest values, in no particular order."""5    heap: list[int] = []                     # min-heap, never more than k items6    for value in numbers:7        heapq.heappush(heap, value)8        if len(heap) > k:9            heapq.heappop(heap)              # evict the smallest of the k + 110    return heap

Line by line: the heap holds the best k values seen so far. Every value is pushed. If that makes k + 1 values, the smallest one leaves, because it cannot be among the k largest. At the end, the heap holds exactly the k largest, and heap[0] is the smallest of them — the k-th largest overall.

The inversion that catches everyone: top K largest uses a MIN-heap. Derive it, don't memorise it. The heap holds your k best candidates. When a new one arrives and the heap is full, you must throw out the worst candidate you hold. For "largest", the worst is the smallest, so the structure must put the smallest on top. That is a min-heap. By the same argument, top K smallest uses a max-heap.

Three more tools finish the kit:

1import heapq23# 1. Custom priority: heapq compares tuples field by field, so put the key first.4heap: list[tuple[int, int, str]] = []5heapq.heappush(heap, (3, 0, "write report"))   # (priority, counter, payload)67# 2. A max-heap where only a min-heap exists: negate the key.8max_heap: list[int] = []9heapq.heappush(max_heap, -42)10largest = -max_heap[0]                         # negate again on the way out1112# 3. Build from a whole list in O(n), not O(n log n).13data = [9, 4, 7, 1]14heapq.heapify(data)                            # data[0] is now 1

The middle field counter in the tuple is a unique tie-breaker. It matters: if two entries have the same priority, Python compares the next field, and if that field is an object with no < defined, the comparison raises TypeError. For tuples you want as a max-heap, negate only the key, (-count, word), never the payload.

Other languages differ. Java's PriorityQueue is a min-heap and takes a comparator. C++'s priority_queue is a max-heap by default — the opposite of Python — and greater<> makes it a min-heap.

Complexity

Why heapify is O(n). It sifts down from the bottom of the tree upwards. Half the nodes are leaves and move zero levels. A quarter can move one level, an eighth two levels, and so on. The total n/4 × 1 + n/8 × 2 + n/16 × 3 + … adds up to about n. Almost every node is near the bottom and has almost nowhere to fall. Saying this in an interview is a small remark that signals depth.

The size-k template costs O(n log k) time and O(k) space. Each of the n values does at most one push and one pop on a heap of size k. With n = 1,000,000 and k = 10, that is about 3.3 million comparisons against 20 million for a full sort, and a 10-slot heap instead of a million-slot copy.

Where it goes wrong

1. A max-heap of everything for top K largest. Heapify all n values into a max-heap and pop k times. It gives the right answer in O(n + k log n) time but O(n) space, and it cannot work on a stream. The size-k min-heap is the answer interviewers want.

2. Reading the array as if it were sorted. heap[0] is the extreme. heap[1] is not the second smallest; it is one child of the root, and the second smallest may be heap[2]. Code that reads past index 0 is almost always wrong, and it passes small tests by luck.

3. Ties. A tie on the priority makes Python compare the next tuple field. If that field is a ListNode or a dict, you get TypeError, but only when values tie, so it survives small tests. Add a unique counter. And a heap is not stable: if the problem says "break ties alphabetically", put that rule into the key, such as (-count, word).

4. Changing an item after it is in the heap. Nothing re-sifts it, so the heap property silently breaks. The fix is lazy deletion: push a fresh entry with the new priority, and when you pop an entry that is out of date, skip it.

5. A heap where something simpler is better. A static array and one query: sort, or use quickselect at O(n) average. k close to n: sort. Counts over a small range: bucket sort in O(n). Say this out loud. "Sorting is O(n log n) and fine here, but if k is small or the data streams, a size-k heap is O(n log k)" — that sentence is most of the topic.