Two Heaps · bigonotes

Two heaps track the middle of a dataset that keeps changing. One heap holds the smaller half, the other holds the larger half, and the median sits at their tops. The same "two pools" shape also shows up when one heap filters what is available and the other picks the best of it.

The idea#

Split the numbers seen so far into two halves:

small: a max-heap (negated values) holding the smaller half. Its top is the largest of the small numbers.
large: a min-heap holding the larger half. Its top is the smallest of the large numbers.

Keep two rules true after every insert:

Order: every number in small is ≤ every number in large.
Balance: the sizes differ by at most 1.

Together they mean the two tops are the middle one or two values. If one heap is bigger, its top is the median; if the sizes are equal, the median is the average of both tops. Each insert is $O(\log n)$ and each median query is $O(1)$ .

Two heaps split a sorted stream: a max-heap holds the small half with its largest value on top, a min-heap holds the large half with its smallest value on top, and the median sits between the two tops

How to spot it#

These cues suggest two heaps.

"Median" of a stream, or of a sliding window.
You need the boundary between the lower and upper part of the data, not the whole order.
Two groups where items move from one to the other: locked vs unlocked projects, waiting vs running jobs.

That last cue points to a second shape: "one heap filters, the other picks". Items wait in one pool until they qualify. Once they qualify, they move into a second heap that ranks them.

Both shapes so far assume numbers only arrive and never leave.

Worth exploring: two heaps over a sliding window (LC 480 Sliding Window Median), where elements leave the window. The removal trick it needs is covered in Heap with Lazy Deletion.

Template#

Route each number by comparing it with the top of small, then rebalance only when the sizes drift apart by 2.

small = empty max-heap        # lower half (store negated values)
large = empty min-heap        # upper half
add(num):
    if small is not empty and num <= top of small:
        push num onto small                # route by value
    else:
        push num onto large
    if len(large) == len(small) + 2:       # balance rule
        move the top of large onto small
    else if len(small) == len(large) + 2:
        move the top of small onto large
median():
    if one heap is bigger: return its top
    return the average of both tops

A short trace makes the routing and rebalancing concrete.

Add	`small` (as values)	`large`	Median	Note
5		5	5	`small` is empty, so 5 goes right
2	2	5	3.5	goes right, sizes 0 vs 2, so the top (2) moves left
8	2	5, 8	5	8 > 2, so it goes right
9	2, 5	8, 9	6.5	goes right, sizes 1 vs 3, so the top (5) moves left

Pitfalls#

The logic is short, so the bugs are mostly small slips.

Sign errors. Values in small are stored negated. Negate when you push, when you pop and when you peek.
Routing against an empty heap. Check that small is not empty before reading its top.
Even vs odd counts. With equal sizes the median is the average of two tops, and it may be a float.
Rebalancing too eagerly or not at all. Move exactly one top across when the size gap reaches 2.
Deleting from the middle. heapq removes only the top. When items must leave from anywhere, plan for that from the start.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Find Median from Data Stream

This is the template as written. Store small negated, route by its top, and rebalance at a size gap of 2.

Hint: Sliding Window Median

The window also has to remove the number that leaves it, and heapq can't delete from the middle. Use lazy removal: remember the outgoing numbers and discard them only when they reach a top. Count balance by valid items, not by raw heap sizes.

Hint: IPO

One heap filters, the other picks. Sort projects by capital (or keep them in a min-heap by capital). Each round, move every newly affordable project into a max-heap by profit, then take the most profitable one. Capital only grows, so an unlocked project stays unlocked.

Key takeaways#

Small half in a max-heap, large half in a min-heap; the median lives at the tops.
Keep two invariants: everything in small ≤ everything in large, and sizes differ by at most 1.
Inserts are $O(\log n)$ , median queries $O(1)$ .
"Filter into one heap, pick from another" is the same shape (IPO).
Removing arbitrary items needs lazy deletion, because heapq only removes the top.

Core idea#

Two heaps track the middle of changing data. A max-heap holds the smaller half and a min-heap holds the larger half, so the median sits at their tops.

Key points#

small: a max-heap of negated values. Its top is the largest small number.
large: a min-heap. Its top is the smallest large number.
Order rule: every number in small is ≤ every number in large.
Balance rule: the sizes differ by at most 1.
Bigger heap: its top is the median. Equal sizes: the average of both tops.
Insert is $O(\log n)$ . Median query is $O(1)$ .
IPO: move newly affordable projects into a max-heap by profit, then take the best. Capital only grows.
Sliding window median needs lazy removal. heapq removes only the top.

Template#

add(num):
    if small is not empty and num <= top of small:
        push num onto small                # route by value
    else:
        push num onto large
    if len(large) == len(small) + 2:       # rebalance at a gap of 2
        move the top of large onto small
    else if len(small) == len(large) + 2:
        move the top of small onto large
median():
    if one heap is bigger: return its top
    return the average of both tops

Pitfalls#

Sign errors. Negate on push, pop and peek for small.
Reading the top of small when it is empty.
Even counts. The median is an average and can be a float.
Rebalancing wrongly. Move exactly one top when the gap reaches 2.

Say it in an interview#

"The small half lives in a max-heap and the large half in a min-heap, so the median is at the tops."
"Inserts are O(log n) and the median is O(1)."