Two Heaps Pattern: How to Build a Median Finder

Why this pattern shows up in interviews

If you can maintain the median of a changing stream of numbers, you understand a core interview pattern: two heaps. The pattern appears in streaming problems, scheduling, percentile tracking, and especially sliding window median questions. It tests whether you can balance competing requirements: fast insertion, fast access to a middle value, and clean invariants.

The key idea is simple, but the implementation rewards careful thinking. You keep the lower half of the numbers in one heap, the upper half in another, and rebalance after each update so the median is always easy to read.

That makes the median finder a great interview problem: it looks like a data-structure question, but really it is about maintaining invariants under repeated updates.

Problem statement

Design a data structure that supports:

• addNum(num): add a number to the data stream
• findMedian(): return the median of all inserted numbers so far

If the count is odd, the median is the middle value. If the count is even, the median is the average of the two middle values.

This is the classic Median Finder problem.

Why a naive approach is not enough

A straightforward solution stores all numbers in a list and sorts them when you need the median.

That works, but it is too slow for a stream:

• inserting is easy
• finding the median after sorting is expensive

In interviews, you usually want to do better than repeatedly sorting the full dataset.

Intuition: split the numbers into two halves

The median sits between two groups:

• the lower half of numbers
• the upper half of numbers

If we can keep those halves balanced, then the median is easy to compute.

That is exactly what two heaps give you:

• a max heap for the lower half
• a min heap for the upper half

In Python, heapq only supports min heaps, so we simulate a max heap by pushing negative values.

Invariants to maintain

After every insertion:

1. Every value in the lower half is less than or equal to every value in the upper half.
2. The two heaps differ in size by at most 1.
3. The lower half can be one element larger than the upper half, but not the other way around if you want a consistent median rule.

With these invariants:

• if the total count is odd, the extra element lives in the lower half, and the median is its top
• if the total count is even, the median is the average of both heap tops

Approach walkthrough

We will use:

• small: max heap for the lower half, stored as negative values
• large: min heap for the upper half

Insertion logic

When a new number arrives:

1. Push it into small first.
2. Move the largest value from small into large.
3. If large becomes larger than small, move its smallest value back into small.

This order keeps the heaps ordered and balanced.

Why this works

Step 1 may place the number into the wrong side temporarily. Step 2 fixes ordering by ensuring the largest lower-half candidate moves into the upper half. Step 3 restores balance if the upper half grew too large.

This is a neat trick: instead of trying to decide the perfect heap up front, you insert and rebalance in a fixed sequence.

Python implementation

import heapq

class MedianFinder:
    def __init__(self):
        # small is a max heap using negative values
        self.small = []
        # large is a standard min heap
        self.large = []

    def addNum(self, num: int) -> None:
        # Step 1: always push to small first
        heapq.heappush(self.small, -num)

        # Step 2: move the largest from small to large
        moved = -heapq.heappop(self.small)
        heapq.heappush(self.large, moved)

        # Step 3: balance sizes so small has at least as many as large
        if len(self.large) > len(self.small):
            moved_back = heapq.heappop(self.large)
            heapq.heappush(self.small, -moved_back)

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return float(-self.small[0])
        return (-self.small[0] + self.large[0]) / 2.0

Worked example 1: inserting an odd number of values

Let’s insert:

[5, 3, 8]

We will track the heaps after each insertion.

After adding 5

• push to small → small = [-5]
• move top of small to large → large = [5], small = []
• rebalance → move 5 back to small

Final state:

• small = [-5]
• large = []

Median: 5

After adding 3

• push to small → small = [-5, -3]
• move top of small to large → move 5, so large = [5], small = [-3]
• rebalance not needed

Final state:

• small = [-3]
• large = [5]

Median: (3 + 5) / 2 = 4.0

After adding 8

• push to small → small = [-8, -3]
• move top of small to large → move 8, so large = [5, 8], small = [-3]
• rebalance → large is bigger, move 5 back to small

Final state:

• small = [-5, -3]
• large = [8]

Median: 5

Notice how the top of small always gives you the lower-middle value.

Worked example 2: duplicates and even counts

Insert:

[1, 2, 2, 3]

This is useful because interview code often fails on duplicate values or even-length streams.

After all insertions

The two heaps end up as:

• small = [-2, -1]
• large = [2, 3]

Median: (2 + 2) / 2 = 2.0

Even with duplicates, the invariant still holds because we only care about ordering between halves, not uniqueness.

Worked example 3: tracing the stream step by step

Insert:

[10, 1, 7, 3, 12]

We can summarize the states:

This is the mental model you want in an interview: the lower half grows in small, the upper half grows in large, and the top elements always describe the middle.

Why the heap order is correct

A common interview question is: why do we push into small first?

Because it simplifies the logic.

Suppose the new number belongs in the upper half. We still push it to small temporarily, then immediately move the largest number from small to large. That guarantees the smallest possible value in the upper half stays there, and any value too large for the lower half gets moved up.

This fixed rebalancing sequence avoids many branchy edge cases.

Alternative approach: insert into the “right” heap directly

You can also compare the number against the top of small and choose a heap directly.

That version is also valid, but it has more conditional logic.

Complexity comparison

The two-heaps approach gives the best balance for streaming median queries.

Common pitfalls

1. Forgetting to rebalance

If the heaps drift apart by more than 1 element, findMedian() becomes wrong.

2. Mixing up max heap and min heap in Python

Remember: heapq is a min heap only.

To simulate a max heap, push -num.

3. Returning the wrong median for even counts

For even counts, you need the average of the two middle values, not one of them.

4. Not preserving the heap invariant

You want all values in small to be less than or equal to all values in large. If you skip the move from small to large, the partition may break.

A slightly cleaner mental model

Think of the heaps like this:

• small stores the left side of the number line
• large stores the right side
• small is allowed to have one extra element

Then:

• odd count → median is top(small)
• even count → median is average of top(small) and top(large)

That is the entire pattern.

Sliding window median: same idea, one extra challenge

The same two-heaps pattern appears in sliding window median.

The difference is that values also leave the window, so you need a way to remove arbitrary elements efficiently. A common solution uses lazy deletion with a hash map alongside the two heaps.

That version is more advanced, but the core invariant is identical:

• lower half in one heap
• upper half in the other
• keep them balanced

If you understand Median Finder, sliding window median becomes much less intimidating.

Another implementation style: explicit balancing helpers

Some people prefer separating the balancing logic into helper methods. It can make interview code easier to explain.

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []
        self.large = []

    def _rebalance(self):
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        elif len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def addNum(self, num: int) -> None:
        if not self.small or num <= -self.small[0]:
            heapq.heappush(self.small, -num)
        else:
            heapq.heappush(self.large, num)

        self._rebalance()

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return float(-self.small[0])
        return (-self.small[0] + self.large[0]) / 2.0

This version is a bit more verbose, but it is easier to reason about in a whiteboard setting because the “where to insert” decision is explicit.

When to reach for two heaps in interviews

Use this pattern when you need:

• a running median
• the k-th smallest around a moving boundary
• a structure that continuously splits data into two ordered groups
• top/bottom halves with efficient updates

You should immediately think about two heaps if the prompt contains words like:

• stream
• running
• median
• percentile
• continuously updated values
• sliding window median

Key takeaways

• Two heaps are the standard way to maintain a dynamic median.
• Use a max heap for the lower half and a min heap for the upper half.
• Keep two invariants: ordering and size balance.
• In Python, simulate the max heap with negative numbers.
• Median Finder is the cleanest entry point to understanding sliding window median and other dual heap problems.

Related problems

Once this pattern feels natural, try these next:

• Sliding Window Median
• Find Median from Data Stream
• Kth Largest Element in a Stream
• Meeting Rooms II
• IPO
• Reorganize String

Practice these next

1. LeetCode 295 — Find Median from Data Stream
2. LeetCode 480 — Sliding Window Median
3. LeetCode 703 — Kth Largest Element in a Stream
4. LeetCode 253 — Meeting Rooms II
5. LeetCode 502 — IPO

If you want to see the heap states and median updates play out visually, I built an interactive version of this walkthrough at codebrew.ai — it can help if you learn best by tracing variables step by step.