cf.completefrontend
HEAPS & PRIORITY QUEUES · CORE

Two heaps (running median)

Split numbers into a lower half kept in a max-heap and an upper half kept in a min-heap, so the middle values are always at the two tops.

Time O(n log n) in total, O(log n) per numberSpace O(n)4 practice problemsStep-through picture

The idea

The median is the middle value of a sorted list: in [1, 3, 8] it is 3, and in a list with an even count it is the average of the two middle values. Keeping the median up to date while numbers keep arriving is hard with one list, because every new number shifts the middle.

Split the numbers into two halves. The lower half goes into a max-heap called low, so its biggest number is on top. The upper half goes into a min-heap called high, so its smallest number is on top. The two tops are the two numbers in the middle.

Keep two rules: every number in low is less than or equal to every number in high, and low has the same number of items as high or exactly one more. Then the median is low's top when the count is odd, or the average of both tops when it is even.

An everyday example

Two teams lined up by height

A class splits into a short team and a tall team, with the short team never more than one person bigger. The tallest of the short team stands at the front of that team, and the shortest of the tall team stands at the front of the other. Those two front people are the middle of the class. When a new student arrives, they join the right team, and if the teams become uneven, the front person of the bigger team switches sides.

How the example maps to the code
In the exampleIn the code
The short team, tallest in frontlow, a max-heap
The tall team, shortest in fronthigh, a min-heap
The new student picks a teamnum <= low.peek() decides
The front person switches sideshigh.push(low.pop()) or low.push(high.pop())
The middle of the classlow.peek() or the average of both tops

From the slow way to two heaps (running median)

  1. The obvious way to report the median after each new number is to keep a sorted array: insert each number in its place, then read the middle. Finding the place is quick with binary search, but inserting shifts up to n items, so each update is O(n), and a stream of n numbers costs O(n²).
  2. The median needs only two numbers: the largest of the smaller half and the smallest of the bigger half. Nothing else about the order matters. So don't keep the halves sorted. Keep the smaller half where its largest item is always on top, and the bigger half where its smallest item is always on top: a max-heap low and a min-heap high.
  3. A new number goes into low if it is at most low's top, and into high otherwise. That keeps every number in low at most every number in high. But the halves can drift apart in size, so after each insert, move one top across if needed: low may hold one more number than high, never two more, and never fewer.
  4. With both rules in place, the two tops sit at the middle of the sorted order: the median is low.peek() alone when the count is odd, or the average of both tops when it is even. Insert on the correct side, rebalance with one move, read the tops: that loop is the two heaps pattern.

How it works

  1. Make low a max-heap ((a, b) => b - a) and high a min-heap ((a, b) => a - b).
  2. For each num, push it into low if low is empty or num <= low.peek(). Otherwise push it into high.
  3. Rebalance: if low has two more items than high, move low's top to high.
  4. If high has more items than low, move high's top to low.
  5. Read the median: low.peek() if low is bigger, otherwise the average of low.peek() and high.peek().

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function runningMedians(nums) {
  2. const low = new MinHeap((a, b) => b - a);
  3. const high = new MinHeap((a, b) => a - b);
  4. const medians = [];
  5. for (const num of nums) {
  6. if (low.size === 0 || num <= low.peek()) low.push(num);
  7. else high.push(num);
  8. if (low.size > high.size + 1) high.push(low.pop());
  9. else if (high.size > low.size) low.push(high.pop());
  10. if (low.size > high.size) medians.push(low.peek());
  11. else medians.push((low.peek() + high.peek()) / 2);
  12. }
  13. return medians;
  14. }

How fast it is

TimeO(n log n) in total, O(log n) per number
Extra memoryO(n)

Each number is pushed once and moved at most a few times, each O(log n). The median is read from the two tops in O(1). Both heaps together hold every number.

  • Best caseO(n log n)

    Even friendly input, like numbers in increasing order, needs a move between heaps about every second number, and each move pops a heap: about log n steps each.

  • Average caseO(n log n)

    Random numbers: each costs a push and sometimes a move, each O(log n), and reading the median is O(1).

  • Worst caseO(n log n)

    Every number causes a push and a move that travel the full height of heaps holding up to n / 2 numbers each.

Common mistakes

  • Using two min-heaps. The lower half needs its biggest item on top, so it must be a max-heap.
  • Choosing the side by comparing with high.peek() when high is empty. Compare with low.peek() and handle the empty case.
  • Forgetting to rebalance after every insert. The sizes drift and the tops stop being the middle values.
  • Using integer division for the even case. (2 + 5) / 2 is 3.5; don't round it unless the problem says so.

When to use it

Look for these clues in a problem:

  • The question asks for the median after each new number, or in every window.
  • You need to split items into a smaller half and a bigger half and keep them balanced.
  • You need the best item from one group while moving items between two groups, like projects you can afford and projects you can't.

Check yourself

Answer each one in your head first, then open it.

Why is low a max-heap and not a min-heap?

The median needs the biggest number of the lower half, so that number has to be on low's top.

After 6 numbers, how many are in each heap?

3 and 3. With an even count the sizes are equal, and the median is the average of the two tops.

Why is one move enough to rebalance?

Each new number changes one heap's size by one, so the size rule can break by at most one step. Moving one top fixes it and keeps the order rule.

In the trace, why didn't adding 6 change the median?

6 went into low below its top, 7. low was then one bigger than high, which is allowed, so the median is still low's top, 7.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Two rules hold after every number: every item in low is at most every item in high (the order rule), and low.size equals high.size or high.size + 1 (the size rule). Together they mean that sorting all the numbers would list low first and high after, with low's top at the middle position and high's top right after it.

Inserting keeps the order rule. A number at most low.peek() goes into low, and since low.peek() was at most everything in high, so is the new number. A number bigger than low.peek() goes into high, and it is bigger than everything in low, because low.peek() is the largest there.

The size rule can break by at most one step, because only one number was added. Moving low's top to high keeps the order rule: it was the biggest in low and at most everything in high, so it becomes high's new smallest. Moving high's top to low works the same way in a mirror. So one move restores both rules, and the median read after it is correct.

Going deeper

3 more ideas

Why the tops are the middle values

Every number in low is at most every number in high, so the sorted list is all of low followed by all of high. low's top is the last number of the lower part and high's top is the first number of the upper part. With sizes equal or low one bigger, those are exactly the middle positions.

Why moving one top is enough

Each new number changes one size by one. So the difference between the sizes can be off by at most one beyond the allowed range, and moving a single top fixes it. Moving a top also keeps the order rule: the biggest of low is still at most everything left in high, and the reverse.

Time and memory

Each new number costs a push and maybe one move between heaps, each O(log n). Reading the median is O(1). Memory is O(n) for all numbers. Sorting after each number would cost O(n log n) each time.

Work it by hand

Every step in a table, with why

Report the median after each of 7 numbers. The heaps are shown as sorted lists to make the halves easy to read.

nums = [7, 3, 12, 10, 1, 15, 6]

StepnumPushed toMovedlowhighMedianWhy
17low-[7][]7low is empty, so 7 goes there. With one number, the median is low's top.
23low7 to high[3][7]53 <= 7, so it joins low, which now has 2 numbers to high's 0. Its top, 7, moves over. The median is (3 + 7) / 2 = 5.
312high7 to low[3, 7][12]712 > 3, so it goes to high, which is now bigger than low. high's top, 7, moves back.
410high-[3, 7][10, 12]8.510 > 7, so it joins high. Equal sizes are allowed. The median is (7 + 10) / 2 = 8.5.
51low-[1, 3, 7][10, 12]71 joins low, which is now one bigger: allowed. The median is low's top, 7.
615high-[1, 3, 7][10, 12, 15]8.515 joins high, and the sizes are equal again.
76low-[1, 3, 6, 7][10, 12, 15]76 <= 7, so it joins low below its top. low's top, and so the median, stays 7.

The medians are [7, 5, 7, 8.5, 7, 8.5, 7]. Only 2 of the 7 numbers needed a move between heaps, and each median was read from the tops without sorting anything.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Two heaps (running median)O(n log n)O(n)Numbers arrive one at a time and you need the median, or a percentile, after each one.
Sorted array with binary insertO(n²)O(n)The stream is short, a few thousand numbers. splice is fast in practice at that size, and the code is simpler.
Sort once at the endO(n log n)O(n)You only need the median once, after all the numbers have arrived.
QuickselectO(n)O(1)You need one median of a full array, not a running one, and may reorder the array. It is O(n) on average.

Extra memory: O(n): the two heaps together hold every number seen, and medians holds one result per number.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Two heaps (running median) and the other approaches, on a scale where each line up is 10 times more steps.
  • Two heaps (running median), Sort once at the end O(n log n)
  • Sorted array with binary insert O(n²)
  • Quickselect O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Two heaps (running median)339,96620 million
Sorted array with binary insert1001 million1 trillion
Sort once at the end339,96620 million
Quickselect101,0001 million

Inputs that need care

5 tricky inputs
One number: [7]
It goes to low, the sizes are 1 and 0, and the median is 7. high.peek() is never read, which matters because it would be undefined.
Equal numbers: [4, 4, 4, 4]
Each 4 passes num <= low.peek() and goes to low, then rebalancing moves one to high. Every median is 4.
Increasing numbers: [1, 2, 3, 4, 5]
Each new number is bigger than low's top, so it goes to high, and every second number causes a move back. The medians are 1, 1.5, 2, 2.5, 3.
Negative numbers and zero: [-3, 0]
Nothing changes: both compares work for any numbers. The second median is (-3 + 0) / 2 = -1.5, which must not be rounded.
Huge values near Number.MAX_VALUE
low.peek() + high.peek() can overflow to Infinity. Use low.peek() / 2 + high.peek() / 2 if values can be that big.

Variations and follow-ups

Twists interviewers add

Sliding window median

For the median of each window of w numbers, add the new number and remove the one leaving. Heaps can't remove from the middle, so record the leaving number in a Map of counts and discard it when it reaches a top (lazy deletion). Keep your own size counts, because the heaps hold some dead items.

Any percentile

To track the 90th percentile instead of the median, keep low at Math.ceil(0.9 * count) items instead of half, moving tops after each insert until that holds. The top of low is then the 90th percentile.

Picking projects with growing capital

Two heaps also fit "choose up to k projects to maximize profit, where each needs some starting money". A min-heap by cost holds the projects you can't afford yet, and a max-heap by profit holds the ones you can. As your money grows, move projects from the first heap to the second, then take the second heap's top.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "median of a data stream", "median after each insertion", "sliding window median", or anything that splits items into a smaller half and a bigger half.
  • State the two rules first: "everything in low is at most everything in high, and low has the same size or one more". Then the code is just keeping those rules after each insert.
  • Handle the empty case when choosing a side: compare with low.peek() only when low isn't empty. Then test by hand with 1, 2, and 3 numbers, and with equal numbers.
  • A common follow-up: "what if all numbers are whole numbers from 0 to 100?". Answer: keep 101 counters and walk them to find the middle count. Each insert is O(1) and each median read is at most 101 steps, with no heaps at all.

Where frontend code uses it

The same idea in real UI code
  • A monitoring dashboard can show the median (p50) response time live as requests come in, without sorting all past timings each time.
  • Smoothing a noisy sensor or frame-time graph with a running median ignores sudden spikes better than an average.
  • Picking the best affordable item while your budget grows (move items from "too expensive" to "affordable" as you earn) uses two heaps the same way.

Related algorithms