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.

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.

Example: 3 largest of six. Given [4, 1, 7, 3, 8, 5] with k = 3, the first three numbers fill the heap to 1, 4, 7 without exceeding the cap, then every push past the cap pops the current minimum: 3 evicts 1, 8 evicts 3, 5 evicts 4. The heap ends holding 5, 7, 8, the three largest, because each eviction removes the one element that can no longer qualify. The visualizer below shows every push and eviction.

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.

Example: running median of a stream. Feed 5, 2, 8, 1, 9: 5 settles in lower for a median of 5, then 2 makes lower one too big, so 5 crosses to upper and the median splits to 3.5. The 8 lands in lower but immediately hops to upper because 8 over upper's 5 breaks max(lower) <= min(upper), and 5 steps back down to even the sizes. The 1 sends 5 back across and the 9 forces two hops (9 up, 5 down), giving medians 5, 3.5, 5, 3.5, 5 - the visualizer below replays every push and rebalance.

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.