Index/Heaps

SponsorGitHub
Coding5 min

Heaps

A tree stored in an array that keeps only one promise: the best element is at the front. Cheaper than sorting, and the right answer whenever a problem says top-k, median, or merge.

What they’re really testing: Recognising that the problem needs the extreme repeatedly, not the full order — and getting the heap's direction and size right.

  • root — the minimum
  • being compared
  • property broken
pythonruns with the steps
1parent = lambda i: (i - 1) // 2
2 
3def push(heap, value):
4    heap.append(value)
5    i = len(heap) - 1
6    while i and heap[parent(i)] > heap[i]:
7        swap(heap, i, parent(i))
8        i = parent(i)
9 
10def pop(heap):
11    top, last = heap[0], heap.pop()
12    if not heap:
13        return top
14    heap[0], i = last, 0
15    n = len(heap)
16    while (c := 2 * i + 1) < n:
17        r = c + 1
18        if r < n and heap[r] < heap[c]:
19            c = r              # smaller child
20        if heap[i] <= heap[c]:
21            break
22        swap(heap, i, c)
23        i = c
24    return top
01 / 11What it ismin 2

A min-heap: a complete binary tree where every parent is smaller than its children. That is a much weaker promise than sorted — only the root is guaranteed to be the minimum, and siblings are in no order at all.

Cost

OperationTimeSpaceWhy
Peek the minimumO(1)O(n)It is the root, which is index 0. This is the operation the whole structure exists for.
Push / popO(log n)—One swap per level while sifting up or down, and the tree's height is log n because it is kept complete.
Build from an array (heapify)O(n)—Sifting down from the last parent backwards. Most nodes are near the bottom and travel almost no distance, so the sum is linear — not O(n log n).
Top-k over n elementsO(n log k)O(k)A heap of size k, pushing each element and evicting the worst. Sorting everything would be O(n log n) and O(n) space.

Reach for it when

  • "K largest", "k closest", "k most frequent" — anything top-k, especially over a stream too big to sort.
  • Scheduling by priority — the next task, the next expiring item, the next event in a simulation.
  • Merging k sorted sequences, where the heap holds one candidate per sequence.
  • Running median, with a max-heap for the low half and a min-heap for the high half.
  • Dijkstra and A*, where the frontier must always yield the cheapest node next.

A weaker promise, bought cheaper

Sorting an array gives total order for O(n log n). Most problems do not need that — they need the best element, repeatedly. A heap provides exactly that and nothing more: the root is the minimum (or maximum), and siblings are unordered.

The structure is a complete binary tree, which means it can be stored in a plain array with no pointers at all:

text
index:   0   1   2   3   4   5   6
value:   2   5   8   9   6  12  10

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

Completeness is what makes that arithmetic valid, and it is why every insert goes at the end and every delete takes from the end.

Two operations, mirrored

Push: append, then sift up while the parent is larger. Pop: take the root, move the last element into its place, then sift down into the smaller child while it is out of order. Both walk one path from root to leaf, so both are O(log n).

python
import heapq


heap = []
heapq.heappush(heap, 5)
smallest = heapq.heappop(heap)
heapq.heapify(existing_list)          # O(n), in place

Use the library in an interview and say what it costs — nobody needs to watch you write sift-down unless they ask.

The top-k pattern

The single most common heap question, and the direction is counterintuitive:

python
def k_largest(nums, k):
    heap = []
    for value in nums:
        heapq.heappush(heap, value)
        if len(heap) > k:
            heapq.heappop(heap)      # drops the smallest survivor
    return heap                       # the k largest, unordered

A min-heap for the k largest. The root is the weakest element still in the running, so it is exactly what should be evicted when a better one arrives. Cost: O(n log k) time, O(k) space — better than sorting on both counts whenever k is small, and it works on a stream that does not fit in memory.

Python's one-sided heap

heapq only does min-heaps. For a max-heap, negate on the way in and out, or push tuples:

python
heapq.heappush(heap, -value)              # max-heap of numbers
heapq.heappush(heap, (-count, word))      # max by count, ties by word

The tuple form is also how you attach a payload to a priority, which is what Dijkstra's frontier needs.

What to say in the interview

Say why a heap instead of sorting: "I only need the extreme repeatedly, so I can pay O(log n) per element instead of ordering everything." For top-k, name the direction and the reason — "min-heap of size k, so the root is the one to evict". Then give the cost as O(n log k) with O(k) space, and mention heapify being O(n) if you are building from an existing array.

Where candidates slip

  • Using the wrong direction. For the k largest you need a min-heap of size k, so the weakest survivor is the one you evict — the instinct to use a max-heap is backwards.
  • Treating the array as sorted. Beyond the root, a heap promises nothing; printing it and expecting order is a common surprise.
  • Building with n pushes when heapify would do. Both give a valid heap, but one is O(n log n) and the other O(n).
  • Forgetting that Python's heapq is a min-heap only. Negate the values, or wrap them in a tuple with an inverted key, and say so out loud.
  • Sifting down to an arbitrary child. You must descend into the smaller child in a min-heap, or the sibling ends up out of order.

Possible follow-up questions

4 questions·try answering before you reveal