Pro

Heaps in Coding Interviews: The Essentials

Heaps are the data structure behind priority queues. They quietly solve a whole family of interview problems.

  1. What a heap is

A heap is a complete binary tree with one extra rule. In a min heap every parent is smaller than or equal to its children, so the smallest value always sits at the root. A max heap flips the rule so the largest value is on top.

  1. How it is stored

Because the tree is complete, it packs neatly into an array with no gaps.

For the node at index i, its children live at 2i + 1 and 2i + 2.

Its parent lives at (i - 1) // 2. No pointers are needed, which keeps heaps fast and memory friendly in practice.

Python ships a min heap in the heapq module.

It works on ordinary lists.

  1. Operations and their costs

Pushing and popping both take O(log n), because a value moves at most one level per step.

Reading the smallest element is O(1): it is always at index 0 of the list.

Turning an existing list into a heap with heapify is O(n).

Sorting would take O(n log n).

Python only has a min heap. For a max heap, push negated values and negate them again when you pop.

Searching for an arbitrary value is still O(n).

A heap only knows where the smallest element is.

  1. Patterns to recognize

Two patterns cover most heap questions: keeping the top k elements, and balancing two heaps to track a median.

Heaps

A complete binary tree where every parent is smaller than or equal to its children (min heap), or larger than or equal to them (max heap).

The smallest element is always at the root, ready in O(1).

Children of index i are at 2i + 1 and 2i + 2. The parent is at (i - 1) // 2.

Heap Operations

Six operations cover almost everything you will do with a heap.

push()

Adds a value at the next open spot, then swaps it upward while it is smaller than its parent.

O(log n)

import heapq
heap = [2, 5, 4, 9, 7, 8]
heapq.heappush(heap, 1)   # 1 rises to the root

pop()

Removes the root, moves the last value to the top, then swaps it downward until the order holds again.

O(log n)

smallest = heapq.heappop(heap)   # returns 2
# 4 is the new root

peek()

Reads the root without removing it.

O(1)

smallest = heap[0]   # no reordering needed

heapify()

Rearranges an existing list into a valid heap in place, working upward from the last parent.

O(n)

nums = [9, 5, 8, 2, 7, 4]
heapq.heapify(nums)   # faster than pushing one by one

len()

Counts the values in the heap.

O(1)

size = len(heap)   # it is just a list

Max heap

Python only provides a min heap. Store negated values to get the largest element on top.

O(log n)

max_heap = []
for x in [2, 9, 4]:
    heapq.heappush(max_heap, -x)
largest = -max_heap[0]   # 9

Heap Patterns

Two Heaps

Keep the smaller half of the numbers in a max heap and the larger half in a min heap. Rebalance so their sizes differ by at most one.

The median is then read straight from the tops of the two heaps.

[1, 3, 4, 6, 8, 9]

Max heap: lower half

Min heap: upper half

Median = (4 + 6) / 2 = 5

Use it for:

  • A running median over a stream of numbers
  • Problems that split values into a low side and a high side

The Top K Pattern

Keep only the k best elements seen so far.

1. Motivation

Say you need the three highest scores from a long list.

The obvious approach is to sort everything in descending order and take the first three.

That works, but sorting costs O(n log n) even though you only care about three values.

Can we do better?

2. A Min Heap of Size k

Keep a min heap that never holds more than k elements.

Push every score. Whenever the heap grows past k, pop the smallest one. What remains are the k largest.

The root is the smallest of the top three, so it is the first to go when a bigger score arrives.

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

3. Complexity

The heap never holds more than k + 1 elements, so each push and pop costs O(log k).

Every one of the n elements is pushed once, for O(n log k) time in total.

The heap itself is the only extra memory, so space is O(k).

When k is much smaller than n, this beats sorting by a wide margin.