Heaps

What is a heap?

A heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is smaller than or equal to its children. In a max-heap, every parent is larger. The root is always the minimum (min-heap) or maximum (max-heap). Because the tree is always complete, it maps cleanly onto an array - no pointers needed.

In Python, heapq implements a min-heap on a plain list. heapq.heappush(heap, val) and heapq.heappop(heap) maintain the heap property after each operation.

import heapq
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
print(heapq.heappop(min_heap))  # 1 - always the minimum

For a max-heap, negate values on push and negate again on pop: heapq.heappush(max_heap, -val), then -heapq.heappop(max_heap).

heapq.heapify(lst) converts an existing list into a heap in O(n) - faster than pushing one by one (O(n log n)) because it works bottom-up and each internal node is sifted down at most once.

The core trade-off: O(1) peek of the extreme value, O(log n) insert and extract. There is no O(1) random access or O(log n) search - the heap property only guarantees the root.

Core operations

Key patterns

Top-K elements

A size-K heap lets you track the K best elements as you scan through arbitrarily large input. The heap acts as a running filter: whenever the heap exceeds K, you discard the element that fails to qualify.

When to use - the problem asks for the K largest, K smallest, or Kth element, but you don't need the rest sorted. Sorting the whole input to read off K is O(n log n); a size-K heap does it in O(n log K), which wins when K is much smaller than n and works even on a stream you can't sort.

How it works - keep a heap capped at size K. After each push, if the heap holds more than K elements, pop the extreme one. The flavor is the counter-intuitive part: to keep the K largest, use a MIN-heap, because its root is the smallest survivor and that is exactly the element to evict when a bigger one arrives. Each element is pushed once and popped at most once, and every heap operation is O(log K), so the whole pass is O(n log K). Remember that Python's heapq is a MIN-heap; to keep the K smallest you negate values on push so the largest survivor sits at the root and gets evicted first.

Two-heap split (running median)

The median is the boundary value between the lower and upper halves of a sorted dataset. Two heaps - a max-heap for the lower half and a min-heap for the upper half - make that boundary accessible in O(1) at any point in a stream.

When to use - you need the running median (or any boundary statistic) of a stream that keeps growing. Re-sorting after every insertion is O(n log n) per query, and even an inserted sorted array costs O(n) per shift. Splitting the data across two heaps holds the boundary at the heap tops, so each insert is O(log n) and each median read is O(1).

How it works - keep the smaller half in a max-heap and the larger half in a min-heap, sized so they differ by at most one element. The invariant is max(lower) <= min(upper): every value in the lower heap sits at or below every value in the upper heap, so the median is either the top of the bigger heap (odd count) or the average of the two tops (even count). On each insert, push first and then rebalance - move a top across if the order breaks, then move one across if the sizes diverge by more than one - which restores both conditions in O(log n). Because Python's heapq is a MIN-heap, the lower half is implemented by negating values on push and negating again on pop so its largest element surfaces at the root.

Canonical examples

K closest points to the origin

The distance from the origin is sqrt(x² + y²), but since sqrt is monotonic, you can compare squared distances directly. Use a max-heap of size K keyed on squared distance: when the heap exceeds K, pop the farthest point. What remains are the K closest.

Find median from data stream

The median is always at the boundary between the lower and upper halves of the data seen so far. A max-heap holds the lower half (top = largest of smaller values) and a min-heap holds the upper half (top = smallest of larger values). Each insertion is O(log n) and each query is O(1).

When to reach for a heap

• The problem asks for the K largest, K smallest, or Kth element in a stream or array.
• You need repeated access to the current minimum or maximum in a set that changes over time.
• The problem involves merging K sorted lists or arrays - a min-heap of (value, list_index) extracts the global minimum in O(log K).
• You need a running median as elements stream in.
• The problem involves scheduling tasks where you always process the highest-priority item next.
• Dijkstra's algorithm requires a priority queue - that is a min-heap keyed on tentative distance.

Practice problems

• Kth Largest Element in an Array - Min-heap of size K; the top is the answer.
• Top K Frequent Elements - Frequency count, then K-largest by frequency using a heap.
• K Closest Points to Origin - Max-heap of size K keyed on squared distance.
• Merge K Sorted Lists - K-way merge with a min-heap; the classic O(n log K) pattern.
• Find Median from Data Stream - Two-heap split; the capstone heap problem.