James Peralta

If you need to repeatedly grab the minimum (or maximum) element, heaps are the data structure you reach for. They power priority queues, scheduling systems, and a surprising number of interview problems.

This post breaks down what heaps are, how they work under the hood, and why their performance characteristics matter — especially for "top K" and "next best" problems.

What is a heap?

A heap is a complete binary tree where every parent is smaller than (or equal to) its children. This is called the min-heap property. The root is always the smallest element.

Flip the rule — every parent is larger than its children — and you get a max-heap.

Some everyday examples:

A hospital ER — the most critical patient is always seen next
A task scheduler — the highest-priority task runs first
"Give me the K largest elements" — keep a min-heap of size K

The heap doesn't fully sort your data. It just guarantees one thing: the top element is the best (smallest or largest). That guarantee is cheap to maintain.

A heap is stored as an array

This is the most surprising thing about heaps. Despite being a tree conceptually, a heap is stored as a flat array. No nodes, no pointers.

The tree structure is implicit. For a node at index i (0-indexed):

Parent and child relationships via index math:

1# Parent of i:2parent = (i - 1) // 23 4# Left child of i:5left = 2 * i + 16 7# Right child of i:8right = 2 * i + 2

Because the tree is complete (every level is full except possibly the last, which fills left to right), there are no gaps in the array. This is why the index math works perfectly.

The tree and its array representation:

1#        12#       / \3#      3    54#     / \5#    7    46#7# Array: [1, 3, 5, 7, 4]8# Index:  0  1  2  3  4

Insert is O(log n)

To insert an element, add it at the end of the array (maintaining completeness), then bubble it up — swap with its parent while it's smaller than its parent.

Insert adds to the end, then bubbles up:

1# Insert 2 into [1, 3, 5, 7, 4]2#3# Step 1: append   → [1, 3, 5, 7, 4, 2]4# Step 2: bubble up → 2 < 5 (parent), swap → [1, 3, 2, 7, 4, 5]5# Step 3: bubble up → 2 > 1 (parent), stop → [1, 3, 2, 7, 4, 5]

The maximum number of swaps is the height of the tree: O(log n).

Extract min (or max) is O(log n)

The minimum is always at the root (index 0). To remove it:

Swap the root with the last element
Remove the last element (now the old root)
Bubble down the new root — swap with the smaller child until the heap property is restored

Extract min removes root, then bubbles down:

1# Extract min from [1, 3, 2, 7, 4, 5]2#3# Step 1: swap root with last → [5, 3, 2, 7, 4, 1]4# Step 2: remove last (1)     → [5, 3, 2, 7, 4]5# Step 3: bubble down 5       → swap with min child (2)6#                              → [2, 3, 5, 7, 4]

Again, maximum height swaps: O(log n).

Peek is O(1)

The min (or max) is always at index 0. Looking at it is free — just read heap[0].

This is the heap's superpower. You always know what the best element is, instantly.

Building a heap from an array is O(n)

You might think building a heap from n elements would be O(n log n) — insert each one at O(log n). But there's a smarter way: heapify.

Start from the last non-leaf node and bubble down each one. Because most nodes are near the bottom (and they barely move), the total work is O(n), not O(n log n).

Heapify an existing list in-place:

1import heapq2 3nums = [5, 3, 8, 1, 2]4heapq.heapify(nums)  # O(n) — nums is now a valid min-heap5# nums → [1, 2, 8, 5, 3]

There is no efficient search

Heaps are not sorted. The only guarantee is the root is the min. To find an arbitrary element, you'd have to scan the entire array: O(n).

If you need fast lookup by value, use a hash set alongside the heap.

When a problem is secretly about heaps

"K largest / K smallest" — keep a min-heap of size K. Anything bigger than the top gets swapped in. O(n log k).

"Kth largest element" — same idea. The top of a min-heap of size K is the Kth largest.

"Top K frequent" — count frequencies first, then use a heap on the counts.

"Merge K sorted lists" — push the head of each list into a min-heap. Pop the smallest, push its successor. The heap always gives you the global minimum across all lists.

"Median from a data stream" — maintain two heaps: a max-heap for the lower half, a min-heap for the upper half. The median is always at one of the two tops.

"Next best" or "cheapest" — any time you repeatedly need the best option from a changing pool, that's a heap.

Know the common heap operations in your language

Python's heapq module operates on a regular list as a min-heap:

heapq.heappush(heap, x) → O(log n)
heapq.heappop(heap) → O(log n)
heap[0] → O(1) (peek)
heapq.heapify(list) → O(n)
heapq.nlargest(k, iterable) → O(n log k)
heapq.nsmallest(k, iterable) → O(n log k)

Python only has a min-heap. For a max-heap, negate the values:

Max-heap trick — negate on push and pop:

1import heapq2 3max_heap = []4heapq.heappush(max_heap, -10)5heapq.heappush(max_heap, -20)6heapq.heappush(max_heap, -5)7 8largest = -heapq.heappop(max_heap)  # → 20

For custom comparators with objects, use tuples: (priority, item). Heapq compares tuples element by element.

Final takeaway

Heaps do one thing and do it fast: give you the best element.

Understanding:

that a heap is a complete binary tree stored as a flat array
that insert and extract are O(log n), peek is O(1)
that Python's heapq is min-heap only — negate for max-heap
the interview cues: "K largest", "top K", "merge K sorted", "median stream", "next best"

will make you fast at recognizing heap problems and confident in implementing them.

Heaps