Heaps

A structure that keeps the smallest or largest item one step away, and the problems where that is exactly what you need

A heap answers one question very fast: what is the smallest item right now?

That is all it does. It cannot tell you if a value exists, it cannot give you sorted order, and it cannot find the second smallest without removing the first. In exchange, it gives you the minimum in O(1) and lets you add or remove in O(log n).

That narrow trade is worth knowing, because a surprising number of problems only ever ask that one question.

The Shape Rule and the Order Rule

A binary heap follows two rules at the same time.

The two rules

Shape — every level is full, left to right, with no gaps.

Order — every parent is smaller than both of its children (a min-heap).

Notice what the order rule does not say. It says nothing about left versus right. 3 may sit to the left of 2, or to the right. Only the parent–child relationship is controlled.

A valid min-heap

1 is the minimum. Every parent is smaller than its children — but 3 sits to the left of 2, and that is fine.

This is why a heap cannot search. To find 9, you would have to check almost every node, because the order rule gives you no way to pick a side.

A Heap Is Really an Array

The shape rule — full levels, no gaps — means a heap can be stored as a plain array with no pointers at all.

index:   0   1   2   3   4   5   6
value:  [1,  3,  2,  7,  5,  4,  9]

For the node at index i:
  parent      →  (i - 1) // 2
  left child  →  2i + 1
  right child →  2i + 2

The same heap, stored flat

▲min

Index 0 is always the answer to 'what is the smallest?'

No node objects, no next pointers, no wasted memory. This is the reason heaps are fast in practice, not just in theory.

Push — Sift Up

Add the new value at the end (keeping the shape rule), then swap it upward until its parent is smaller.

Pushing 0 into the heap

Place 0 at the first free slot. The shape rule is satisfied, but the order rule is now broken — 0 is below 7.

1 / 4

The new value travels at most one level per step, so a push costs O(log n).

Pop — Sift Down

Removing the minimum is the same trick upside down. You cannot just delete the root — that would leave a hole. So move the last item into the root, then swap it downward.

Popping the minimum

0 is the answer we are about to return. But we cannot leave a hole at the root.

1 / 4

Always swap with the smaller child. Picking the bigger one silently breaks the heap.

The most common sift-down bug

When sifting down, you must compare against both children and swap with the smaller. If you only compare against the left child, or swap with whichever you checked first, the heap stays broken and every later pop returns wrong answers — with no crash to tell you.

Cost Summary

Operation	Cost	Why
Peek at the minimum	`O(1)`	It is always at index 0
Push	`O(log n)`	At most one swap per level
Pop the minimum	`O(log n)`	At most one swap per level
Build from `n` items	`O(n)`	Not `O(n log n)` — see below
Find an arbitrary value	`O(n)`	No search ability at all

Why building a heap is O(n), not O(n log n)

Pushing n items one at a time costs O(n log n). But heapify — starting from the middle of the array and sifting down — costs only O(n).

The reason is that most nodes are near the bottom. Half the nodes are leaves and need zero work; a quarter sit one level up and need at most one swap. The total adds up to less than 2n.

Both Python's heapq.heapify and a hand-written loop use this. If you are building from a full list, always heapify instead of pushing in a loop.

Using a Heap in Each Language

import heapq

# Python's heapq is a MIN-heap operating on a plain list.
nums = [5, 1, 8, 3]
heapq.heapify(nums)          # O(n) — nums is now [1, 3, 8, 5]

heapq.heappush(nums, 0)      # O(log n)
smallest = nums[0]           # O(1) peek, does not remove
smallest = heapq.heappop(nums)  # O(log n), removes and returns 0

# There is no max-heap. Negate the values to fake one.
max_heap: list[int] = []
for value in [5, 1, 8]:
    heapq.heappush(max_heap, -value)
largest = -heapq.heappop(max_heap)  # 8

# For (priority, item) pairs, ties fall through to the second element —
# so the item itself must be comparable, or add a counter to break ties.
tasks = [(2, "write"), (1, "read")]
heapq.heapify(tasks)

Language differences that bite

Python has no max-heap. Push -value and negate on the way out. With tuples, negate only the sort key: (-count, word).

JavaScript has no heap at all. You must write one, or sort instead. In practice, if n is small, sorting is often the pragmatic choice.

Python tuple ties. heappush(heap, (count, item)) compares item when counts are equal. If item is not comparable — a dictionary, say — this raises TypeError only on the unlucky input that ties.

When to Reach for a Heap

The signal is almost always the phrase "the k best" or "the next one to process".

The problem says…	Why a heap fits
"the `k` largest / smallest"	Keep a heap of size `k`; everything else is discarded as it arrives
"merge these sorted lists"	The next output is always the smallest head
"the median as numbers stream in"	Two heaps, one for each half
"process the closest / cheapest next"	The core of Dijkstra's algorithm

The size-k trick

To find the k largest values, keep a min-heap of size k — not a max-heap.

It feels backwards, but the minimum of that heap is the weakest survivor. When a new value arrives, compare it against the weakest: if the newcomer is bigger, evict the weakest. The heap never grows past k, so the cost is O(n log k) instead of O(n log n).

Problems

Kth Largest Element in an Array — the size-k trick, and why sorting is sometimes still the right call
Merge k Sorted Lists — a heap of list heads
Top K Frequent Elements — counting first, then choosing between a heap and bucket sort

Trees — a heap is a binary tree, but with a completely different rule
Sorting — heapsort is just "pop everything, in order"
Design — heaps show up whenever an operation must stay O(log n)

Heaps

On this page