Two Heaps

Overview

The two-heaps pattern splits a set of numbers into a lower half and an upper half. A max-heap holds the lower half, so its root is the largest small value. A min-heap holds the upper half, so its root is the smallest large value. The median of the whole set is then always at one root or the other, or the average of both.

The pattern answers one question well: what is the middle of the data right now, while values keep arriving? Sorting after every insert costs O(n log n) each time; a sorted list costs O(n) per insert because it shifts elements. Two heaps cost O(log n) per insert and O(1) per median query.

The two invariants

• Order — every value in the lower heap is at most every value in the upper heap — the roots are the two values next to the middle
• Size — the heaps are the same size, or the lower one has one extra — the middle is at a root, not somewhere inside a heap

If either rule breaks, the roots stop being the median. Both must hold after every insert.

Adding a value

The simplest routing that keeps both rules is: push the new value into the lower heap, move the lower heap's largest value to the upper heap, and if the upper heap is now bigger, move its smallest value back. Two or three heap operations, all O(log n).

Trace for the stream 6, 10, 2, 6, 5, 0. Both heaps are shown sorted so the halves are easy to read; only the roots (the last lower value and the first upper value) are what the code sees.

• 6 — 6 — 1, 0 — 6
• 10 — 6 — 10 — 1, 1 — (6 + 10) / 2 = 8
• 2 — 2, 6 — 10 — 2, 1 — 6
• 6 — 2, 6 — 6, 10 — 2, 2 — (6 + 6) / 2 = 6
• 5 — 2, 5, 6 — 6, 10 — 3, 2 — 6
• 0 — 0, 2, 5 — 6, 6, 10 — 3, 3 — (5 + 6) / 2 = 5.5

Reading the median

• Odd — the root of the lower heap (it has the extra value) — after 5: lower root 6
• Even — the average of both roots — after 0: (5 + 6) / 2

Duplicates are fine: the value 6 sits in both heaps after the fourth insert and the median is still right. In Python, heapq is a min-heap, so the lower heap stores negated values; Python 3.14 adds heappush_max and heappop_max if you prefer a real max-heap.

Sliding window median: lazy deletion

Sliding Window Median asks for the median of each window of k values as the window moves one step at a time. Adding the new value is the same as before. Removing the value that left the window is the problem: a binary heap cannot delete from the middle in O(log n).

The fix is lazy deletion. Do not remove the old value; record it as stale in a counter. Keep two counts of live values, one per heap, and use those counts, not the heap lengths, for the size rule. Whenever a stale value reaches a root, pop it then. Stale values below the roots do no harm because they never affect the roots' values.

Trace for nums = 1, 3, -1, -3, 5, 3, 6, 7 with k = 3. The window column shows the live values; stale values that are still physically in a heap are not shown.

• 1, 3, -1 — -1, 1 — 3 — 1
• 3, -1, -3 — -3, -1 — 3 — -1
• -1, -3, 5 — -3, -1 — 5 — -1
• -3, 5, 3 — -3, 3 — 5 — 3
• 5, 3, 6 — 3, 5 — 6 — 5
• 3, 6, 7 — 3, 6 — 7 — 6

Each step does a constant number of heap operations, but stale values make the heaps larger than k, so each operation is O(log n) rather than O(log k). Total: O(n log n).

The IPO variant: two heaps with different keys

IPO gives projects with a cost and a profit, a starting capital, and a limit of k projects. Each project you finish adds its profit to your capital. The two heaps here hold different things: a min-heap of projects by cost, and a max-heap by profit of the projects you can currently afford.

Trace with k = 2, capital 0, profits 1, 2, 3 and costs 0, 1, 1.

• 1 — 0 — (0, 1) — 1 — 1 — 1
• 2 — 1 — (1, 2), (1, 3) — 2, 3 — 3 — 4

Every project enters and leaves each heap at most once, so the time is O((n + k) log n): sorting or heaping the projects by cost costs O(n log n), and each of the k picks costs O(log n).

Alternatives

• Two heaps — O(log n) — O(1) — not directly; lazy deletion — streams, windows
• Sorted list with bisect — O(n) shift — O(1) by index — O(n) shift — small windows; simplest to write
• Balanced tree with subtree sizes — O(log n) — O(log n) — O(log n) — any percentile, not just the median
• Sort everything at the end — O(n log n) once — O(1) — all data known up front

For the sliding window, the sorted-list version with bisect is O(n k) overall and often the quickest to get right; say that you know the two-heap version and why it is O(n log n).

What you will be able to do

• State the two invariants and show, on a short stream, that each insert keeps both.
• Write a running median in O(log n) per insert and O(1) per query.
• Explain lazy deletion and why live counts, not heap lengths, drive the balance in a sliding window.
• Recognize the IPO shape: two heaps keyed on different fields.
• Compare two heaps with a sorted list and a balanced tree and say when each is the better answer.

When to use it

• The median of a stream of numbers, updated after every insert
• The median of each sliding window of fixed size
• Any split of data into a lower and an upper part where you need the boundary values quickly
• Greedy problems where one heap feeds another as items become eligible, such as IPO
• A fixed percentile of a stream, by keeping the two heaps in a fixed size ratio

More Coding & DSA topics

• String DP
• Top K Elements
• Topological Sort
• Tree Traversals
• Trees
• Tries
• Two Pointers
• Union Find