27.04Intermediate / Advanced4 topics17 min4 interactive animations

Dual heap problems

Two heaps working together: the online median, the sliding-window median, lazy deletion and keeping the two heaps balanced.

Learning goals

Maintain a median with a max-heap and a min-heap
Keep the two heaps balanced after every insertion
Remove elements from a heap lazily when they leave a sliding window
Compute the median of every window of a stream

Prerequisites

Heap algorithm design

The median splits the data in half. Keeping the lower half in a max-heap and the upper half in a min-heap puts both halves' boundary elements, the ones that define the median, at the two tops.

27.04.1

Online median

To track the median of a growing stream, keep the **smaller half** in a max-heap lo and the **larger half** in a min-heap hi, sizes equal or lo larger by one. Then the median is the top of lo (odd count) or the mean of the two tops (even count), in O(1). Insert a value into the correct heap by comparing with lo's top, then **rebalance** by moving one top across if the sizes differ too much.

In the animation's “Mixed stream” preset the final count is even and the median is (7 + 8) / 2 = 7.5; with an odd count it is the top of the lower heap.

Java

1static class MedianFinder {
2    private final PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());   // smaller half
3    private final PriorityQueue<Integer> hi = new PriorityQueue<>();                             // larger half
4    void add(int x) {
5        if (lo.isEmpty() || x <= lo.peek()) lo.add(x); else hi.add(x);
6        if (lo.size() > hi.size() + 1) hi.add(lo.poll());        // keep sizes equal, or lo one bigger
7        else if (hi.size() > lo.size()) lo.add(hi.poll());
8    }
9    double median() {
10        return lo.size() > hi.size() ? lo.peek() : ((double) lo.peek() + hi.peek()) / 2;
11    }
12}

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space

O(n)

Running median with two heaps

Interactive · edit the input

stream

151

107

low (max-heap)

empty

high (min-heap)

empty

medians so far

empty

Setup

Split the numbers seen so far into a lower half (max-heap, top = largest of the lower half) and an upper half (min-heap, top = smallest of the upper half). The median sits at the two tops. Heaps are drawn with their top first.

Step 1 / 37

Java

1class MedianFinder {
2    PriorityQueue<Integer> low  = new PriorityQueue<>(Comparator.reverseOrder()); // max-heap
3    PriorityQueue<Integer> high = new PriorityQueue<>();                          // min-heap
4
5    void add(int x) {
6        low.add(x);
7        high.add(low.poll());                 // every low value <= every high value
8        if (high.size() > low.size()) {
9            low.add(high.poll());             // keep low the same size or one larger
10        }
11    }
12
13    double median() {
14        return low.size() > high.size() ? low.peek() : (low.peek() + high.peek()) / 2.0;
15    }
16}

Live state

0 inserted

low.size

high.size

No condition evaluated on this step

Execution trace (dry run table)Show 37 steps

Step	Line	State	What happens
1	L1	low.size=0 high.size=0	Split the numbers seen so far into a lower half (max-heap, top = largest of the lower half) and an upper half (min-heap, top = smallest of the upper half). The median sits at the two tops. Heaps are drawn with their top first.
2	L6	x=5 low.size=1 high.size=0	low.add(5). The new value always enters the lower half first.
3	L7	x=5 moved=5 low.size=0 high.size=1	high.add(low.poll()): the largest value of the lower half (5) moves up. This guarantees every low value is <= every high value.
4	L8	low.size=0 high.size=1	The upper half is bigger than the lower half, so rebalance.
5	L9	moved=5 low.size=1 high.size=0	Move 5 back to the lower half.
6	L14	median=5 low.size=1 high.size=0	Odd count: the median is the top of low, 5.
7	L6	x=15 low.size=2 high.size=0	low.add(15). The new value always enters the lower half first.
8	L7	x=15 moved=15 low.size=1 high.size=1	high.add(low.poll()): the largest value of the lower half (15) moves up. This guarantees every low value is <= every high value.
9	L8	low.size=1 high.size=1	Sizes are balanced: low is equal or one larger.
10	L14	median=10 low.size=1 high.size=1	Even count: the median is the average of the two tops, (5 + 15) / 2 = 10.
11	L6	x=1 low.size=2 high.size=1	low.add(1). The new value always enters the lower half first.
12	L7	x=1 moved=5 low.size=1 high.size=2	high.add(low.poll()): the largest value of the lower half (5) moves up. This guarantees every low value is <= every high value.
13	L8	low.size=1 high.size=2	The upper half is bigger than the lower half, so rebalance.
14	L9	moved=5 low.size=2 high.size=1	Move 5 back to the lower half.
15	L14	median=5 low.size=2 high.size=1	Odd count: the median is the top of low, 5.
16	L6	x=3 low.size=3 high.size=1	low.add(3). The new value always enters the lower half first.
17	L7	x=3 moved=5 low.size=2 high.size=2	high.add(low.poll()): the largest value of the lower half (5) moves up. This guarantees every low value is <= every high value.
18	L8	low.size=2 high.size=2	Sizes are balanced: low is equal or one larger.
19	L14	median=4 low.size=2 high.size=2	Even count: the median is the average of the two tops, (3 + 5) / 2 = 4.
20	L6	x=8 low.size=3 high.size=2	low.add(8). The new value always enters the lower half first.
21	L7	x=8 moved=8 low.size=2 high.size=3	high.add(low.poll()): the largest value of the lower half (8) moves up. This guarantees every low value is <= every high value.
22	L8	low.size=2 high.size=3	The upper half is bigger than the lower half, so rebalance.
23	L9	moved=5 low.size=3 high.size=2	Move 5 back to the lower half.
24	L14	median=5 low.size=3 high.size=2	Odd count: the median is the top of low, 5.
25	L6	x=7 low.size=4 high.size=2	low.add(7). The new value always enters the lower half first.
26	L7	x=7 moved=7 low.size=3 high.size=3	high.add(low.poll()): the largest value of the lower half (7) moves up. This guarantees every low value is <= every high value.
27	L8	low.size=3 high.size=3	Sizes are balanced: low is equal or one larger.
28	L14	median=6 low.size=3 high.size=3	Even count: the median is the average of the two tops, (5 + 7) / 2 = 6.
29	L6	x=9 low.size=4 high.size=3	low.add(9). The new value always enters the lower half first.
30	L7	x=9 moved=9 low.size=3 high.size=4	high.add(low.poll()): the largest value of the lower half (9) moves up. This guarantees every low value is <= every high value.
31	L8	low.size=3 high.size=4	The upper half is bigger than the lower half, so rebalance.
32	L9	moved=7 low.size=4 high.size=3	Move 7 back to the lower half.
33	L14	median=7 low.size=4 high.size=3	Odd count: the median is the top of low, 7.
34	L6	x=10 low.size=5 high.size=3	low.add(10). The new value always enters the lower half first.
35	L7	x=10 moved=10 low.size=4 high.size=4	high.add(low.poll()): the largest value of the lower half (10) moves up. This guarantees every low value is <= every high value.
36	L8	low.size=4 high.size=4	Sizes are balanced: low is equal or one larger.
37	L14	median=7.5 low.size=4 high.size=4	Even count: the median is the average of the two tops, (7 + 8) / 2 = 7.5.

27.04.2

Sliding-window median

For the median of every window of k values, each step adds the new value and removes the one that left the window. Adding is as before. **Removing** an arbitrary value from a heap costs O(k), so the whole algorithm would be O(n · k). The next lesson's trick, **lazy deletion**, brings the cost to O(log k) per slide.

The animation shows the two heaps as arrays, the window shaded in the input, and the stale values waiting to be discarded. On the input 5, 2, 9, 3, 8, 1, 7 with k = 3 the medians are [5, 3, 8, 3, 7]; with k = 4 (even window) they are [4, 5.5, 5.5, 5], where each is the mean of the two tops.

Sliding window median with two heaps and lazy deletion

Interactive · edit the input

input (window shaded)

lower half: max-heap, 0 live

none

upper half: min-heap, 0 live

none

waiting to be deleted (value × copies)

none

medians so far

none

Setup

Keep the smaller half of the window in a max-heap and the larger half in a min-heap, sizes equal or differing by one: the median is a top. Removing the element that leaves the window is done lazily.

Step 1 / 29

Java

1static PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()), hi = new PriorityQueue<>();
2static Map<Integer, Integer> delayed = new HashMap<>();     // value -> copies waiting to be deleted lazily
3static int loSize, hiSize;                                  // live elements, not counting stale ones
4static void prune(PriorityQueue<Integer> h) {
5    while (!h.isEmpty() && delayed.getOrDefault(h.peek(), 0) > 0) {
6        delayed.merge(h.peek(), -1, Integer::sum);          // the stale top is finally removed
7        h.poll();
8    }
9}
10static void rebalance() {                        // keep loSize == hiSize or loSize == hiSize + 1
11    if (loSize > hiSize + 1) { hi.add(lo.poll()); loSize--; hiSize++; prune(lo); }
12    else if (loSize < hiSize) { lo.add(hi.poll()); loSize++; hiSize--; prune(hi); }
13}
14static void add(int x) {
15    if (lo.isEmpty() || x <= lo.peek()) { lo.add(x); loSize++; } else { hi.add(x); hiSize++; }
16    rebalance();
17}
18static void remove(int x) {                      // O(log n) instead of an O(n) removal
19    delayed.merge(x, 1, Integer::sum);           // just remember it
20    if (x <= lo.peek()) { loSize--; if (x == lo.peek()) prune(lo); }
21    else { hiSize--; if (!hi.isEmpty() && x == hi.peek()) prune(hi); }
22    rebalance();
23}
24static double median(int k) { return k % 2 == 1 ? lo.peek() : ((double) lo.peek() + hi.peek()) / 2; }

Live state

0 stale removed

lower live

upper live

No condition evaluated on this step

Execution trace (dry run table)Show 29 steps

Step	Line	State	What happens
1	L1	lower live=0 upper live=0	Keep the smaller half of the window in a max-heap and the larger half in a min-heap, sizes equal or differing by one: the median is a top. Removing the element that leaves the window is done lazily.
2	L14	lower live=1 upper live=0	Add 1: it is at most the lower top, so it joins the lower half.
3	L14	lower live=1 upper live=1	Add 3: it is above the lower top, so it joins the upper half.
4	L14	lower live=1 upper live=2	Add 2: it is above the lower top, so it joins the upper half.
5	L11	lower live=2 upper live=1	The upper half is bigger: move its top 2 to the lower half.
6	L22	lower live=2 upper live=1	Window [1, 3, 2]: the median is 2 (the lower top).
7	L14	lower live=2 upper live=2	Add 8: it is above the lower top, so it joins the upper half.
8	L18	lower live=1 upper live=2	Remove 1: do not search the heap (that costs O(n)); just note it as stale. It belongs to the lower half, so that half has one fewer live element.
9	L11	lower live=2 upper live=1	The upper half is bigger: move its top 3 to the lower half.
10	L22	lower live=2 upper live=1	Window [3, 2, 8]: the median is 3 (the lower top).
11	L14	lower live=2 upper live=2	Add 5: it is above the lower top, so it joins the upper half.
12	L18	lower live=1 upper live=2	Remove 3: do not search the heap (that costs O(n)); just note it as stale. It belongs to the lower half, so that half has one fewer live element.
13	L5	lower live=1 upper live=2	The top 3 is stale (it left the window earlier): discard it now.
14	L11	lower live=2 upper live=1	The upper half is bigger: move its top 5 to the lower half.
15	L22	lower live=2 upper live=1	Window [2, 8, 5]: the median is 5 (the lower top).
16	L14	lower live=3 upper live=1	Add 3: it is at most the lower top, so it joins the lower half.
17	L10	lower live=2 upper live=2	The lower half is too big: move its top 5 to the upper half.
18	L18	lower live=1 upper live=2	Remove 2: do not search the heap (that costs O(n)); just note it as stale. It belongs to the lower half, so that half has one fewer live element.
19	L11	lower live=2 upper live=1	The upper half is bigger: move its top 5 to the lower half.
20	L22	lower live=2 upper live=1	Window [8, 5, 3]: the median is 5 (the lower top).
21	L14	lower live=2 upper live=2	Add 6: it is above the lower top, so it joins the upper half.
22	L19	lower live=2 upper live=1	Remove 8: note it as stale. It belongs to the upper half, so that half has one fewer live element.
23	L22	lower live=2 upper live=1	Window [5, 3, 6]: the median is 5 (the lower top).
24	L14	lower live=2 upper live=2	Add 7: it is above the lower top, so it joins the upper half.
25	L18	lower live=1 upper live=2	Remove 5: do not search the heap (that costs O(n)); just note it as stale. It belongs to the lower half, so that half has one fewer live element.
26	L5	lower live=1 upper live=2	The top 5 is stale (it left the window earlier): discard it now.
27	L11	lower live=2 upper live=1	The upper half is bigger: move its top 6 to the lower half.
28	L22	lower live=2 upper live=1	Window [3, 6, 7]: the median is 6 (the lower top).
29	L22	windows=6	Medians of every window of 3: [2, 3, 5, 5, 5, 6]. Each slide costs O(log k).

27.04.3

Lazy deletion

**Lazy deletion** postpones removal: when a value leaves the window, do not search for it, just record it in a map of 'values to delete' (a count per value) and adjust the live sizes of the heap it belongs to. Stale values are discarded only when they reach the **top** of their heap, where removing them is an ordinary O(log k) poll. The heaps may hold stale values, so size() is replaced by the live counts.

The rule that keeps it correct: always **prune** a heap's top after anything that could expose a stale value, namely after a removal from that heap and after moving its top to the other heap. The animation's “waiting to be deleted” row lists the stale copies, and its “Duplicates” preset shows why a count per value, not a set, is needed.

Java

1static PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()), upper = new PriorityQueue<>();
2static Map<Integer, Integer> delayed = new HashMap<>();     // value -> copies waiting to be deleted lazily
3static int lowerSize, upperSize;                                  // live elements, not counting stale ones
4static void prune(PriorityQueue<Integer> h) {
5    while (!h.isEmpty() && delayed.getOrDefault(h.peek(), 0) > 0) {
6        delayed.merge(h.peek(), -1, Integer::sum);          // the stale top is finally removed
7        h.poll();
8    }
9}
10static void rebalance() {                        // keep lowerSize == upperSize or lowerSize == upperSize + 1
11    if (lowerSize > upperSize + 1) { upper.add(lower.poll()); lowerSize--; upperSize++; prune(lower); }
12    else if (lowerSize < upperSize) { lower.add(upper.poll()); lowerSize++; upperSize--; prune(upper); }
13}
14static void add(int x) {
15    if (lower.isEmpty() || x <= lower.peek()) { lower.add(x); lowerSize++; } else { upper.add(x); upperSize++; }
16    rebalance();
17}
18static void remove(int x) {                      // O(log n) instead of an O(n) removal
19    delayed.merge(x, 1, Integer::sum);           // just remember it
20    if (x <= lower.peek()) { lowerSize--; if (x == lower.peek()) prune(lower); }
21    else { upperSize--; if (!upper.isEmpty() && x == upper.peek()) prune(upper); }
22    rebalance();
23}
24static double median(int k) { return k % 2 == 1 ? lower.peek() : ((double) lower.peek() + upper.peek()) / 2; }
25static double[] windowMedians(int[] a, int k) {
26    lower.clear(); upper.clear(); delayed.clear(); lowerSize = 0; upperSize = 0;
27    double[] out = new double[a.length - k + 1];
28    for (int i = 0; i < k; i++) add(a[i]);
29    for (int i = k; ; i++) {
30        out[i - k] = median(k);
31        if (i == a.length) break;
32        add(a[i]);                               // the new value enters, then the oldest one leaves
33        remove(a[i - k]);
34    }
35    return out;
36}

Best

O(n log k)

Average

O(n log k)

Worst

O(n log k)

Space

O(n)

Sliding window median with two heaps and lazy deletion

Interactive · edit the input

input (window shaded)

lower half: max-heap, 0 live

none

upper half: min-heap, 0 live

none

waiting to be deleted (value × copies)

none

medians so far

none

Setup

Keep the smaller half of the window in a max-heap and the larger half in a min-heap, sizes equal or differing by one: the median is a top. Removing the element that leaves the window is done lazily.

Step 1 / 29

Java

1static PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()), hi = new PriorityQueue<>();
2static Map<Integer, Integer> delayed = new HashMap<>();     // value -> copies waiting to be deleted lazily
3static int loSize, hiSize;                                  // live elements, not counting stale ones
4static void prune(PriorityQueue<Integer> h) {
5    while (!h.isEmpty() && delayed.getOrDefault(h.peek(), 0) > 0) {
6        delayed.merge(h.peek(), -1, Integer::sum);          // the stale top is finally removed
7        h.poll();
8    }
9}
10static void rebalance() {                        // keep loSize == hiSize or loSize == hiSize + 1
11    if (loSize > hiSize + 1) { hi.add(lo.poll()); loSize--; hiSize++; prune(lo); }
12    else if (loSize < hiSize) { lo.add(hi.poll()); loSize++; hiSize--; prune(hi); }
13}
14static void add(int x) {
15    if (lo.isEmpty() || x <= lo.peek()) { lo.add(x); loSize++; } else { hi.add(x); hiSize++; }
16    rebalance();
17}
18static void remove(int x) {                      // O(log n) instead of an O(n) removal
19    delayed.merge(x, 1, Integer::sum);           // just remember it
20    if (x <= lo.peek()) { loSize--; if (x == lo.peek()) prune(lo); }
21    else { hiSize--; if (!hi.isEmpty() && x == hi.peek()) prune(hi); }
22    rebalance();
23}
24static double median(int k) { return k % 2 == 1 ? lo.peek() : ((double) lo.peek() + hi.peek()) / 2; }

Live state

0 stale removed

lower live

upper live

No condition evaluated on this step

Execution trace (dry run table)Show 29 steps

Step	Line	State	What happens
1	L1	lower live=0 upper live=0	Keep the smaller half of the window in a max-heap and the larger half in a min-heap, sizes equal or differing by one: the median is a top. Removing the element that leaves the window is done lazily.
2	L14	lower live=1 upper live=0	Add 1: it is at most the lower top, so it joins the lower half.
3	L14	lower live=1 upper live=1	Add 3: it is above the lower top, so it joins the upper half.
4	L14	lower live=1 upper live=2	Add 2: it is above the lower top, so it joins the upper half.
5	L11	lower live=2 upper live=1	The upper half is bigger: move its top 2 to the lower half.
6	L22	lower live=2 upper live=1	Window [1, 3, 2]: the median is 2 (the lower top).
7	L14	lower live=2 upper live=2	Add 8: it is above the lower top, so it joins the upper half.
8	L18	lower live=1 upper live=2	Remove 1: do not search the heap (that costs O(n)); just note it as stale. It belongs to the lower half, so that half has one fewer live element.
9	L11	lower live=2 upper live=1	The upper half is bigger: move its top 3 to the lower half.
10	L22	lower live=2 upper live=1	Window [3, 2, 8]: the median is 3 (the lower top).
11	L14	lower live=2 upper live=2	Add 5: it is above the lower top, so it joins the upper half.
12	L18	lower live=1 upper live=2	Remove 3: do not search the heap (that costs O(n)); just note it as stale. It belongs to the lower half, so that half has one fewer live element.
13	L5	lower live=1 upper live=2	The top 3 is stale (it left the window earlier): discard it now.
14	L11	lower live=2 upper live=1	The upper half is bigger: move its top 5 to the lower half.
15	L22	lower live=2 upper live=1	Window [2, 8, 5]: the median is 5 (the lower top).
16	L14	lower live=3 upper live=1	Add 3: it is at most the lower top, so it joins the lower half.
17	L10	lower live=2 upper live=2	The lower half is too big: move its top 5 to the upper half.
18	L18	lower live=1 upper live=2	Remove 2: do not search the heap (that costs O(n)); just note it as stale. It belongs to the lower half, so that half has one fewer live element.
19	L11	lower live=2 upper live=1	The upper half is bigger: move its top 5 to the lower half.
20	L22	lower live=2 upper live=1	Window [8, 5, 3]: the median is 5 (the lower top).
21	L14	lower live=2 upper live=2	Add 6: it is above the lower top, so it joins the upper half.
22	L19	lower live=2 upper live=1	Remove 8: note it as stale. It belongs to the upper half, so that half has one fewer live element.
23	L22	lower live=2 upper live=1	Window [5, 3, 6]: the median is 5 (the lower top).
24	L14	lower live=2 upper live=2	Add 7: it is above the lower top, so it joins the upper half.
25	L18	lower live=1 upper live=2	Remove 5: do not search the heap (that costs O(n)); just note it as stale. It belongs to the lower half, so that half has one fewer live element.
26	L5	lower live=1 upper live=2	The top 5 is stale (it left the window earlier): discard it now.
27	L11	lower live=2 upper live=1	The upper half is bigger: move its top 6 to the lower half.
28	L22	lower live=2 upper live=1	Window [3, 6, 7]: the median is 6 (the lower top).
29	L22	windows=6	Medians of every window of 3: [2, 3, 5, 5, 5, 6]. Each slide costs O(log k).

27.04.4

Two-heap balancing

Balancing is one invariant, **|lo| equals |hi| or exceeds it by one**, restored by moving at most one element after each change: from lo to hi when lo is too big, from hi to lo when hi is bigger. Moving the **top** is always safe, because the top of the max-heap is the largest of the lower half, so it is also the smallest candidate for the upper half, and vice versa.

The same two-heap structure answers any 'order statistic at a fixed fraction' query (the median, the 25th percentile if the heaps are kept 1 : 3), and generalises to a sliding window with lazy deletion as above. The “Mixed stream” and “Increasing” presets of the median animation show the transfers between the two heaps.

Running median with two heaps

Interactive · edit the input

stream

151

107

low (max-heap)

empty

high (min-heap)

empty

medians so far

empty

Setup

Step 1 / 37

Java

1class MedianFinder {
2    PriorityQueue<Integer> low  = new PriorityQueue<>(Comparator.reverseOrder()); // max-heap
3    PriorityQueue<Integer> high = new PriorityQueue<>();                          // min-heap
4
5    void add(int x) {
6        low.add(x);
7        high.add(low.poll());                 // every low value <= every high value
8        if (high.size() > low.size()) {
9            low.add(high.poll());             // keep low the same size or one larger
10        }
11    }
12
13    double median() {
14        return low.size() > high.size() ? low.peek() : (low.peek() + high.peek()) / 2.0;
15    }
16}

Live state

0 inserted

low.size

high.size

No condition evaluated on this step

Execution trace (dry run table)Show 37 steps

Step	Line	State	What happens
1	L1	low.size=0 high.size=0	Split the numbers seen so far into a lower half (max-heap, top = largest of the lower half) and an upper half (min-heap, top = smallest of the upper half). The median sits at the two tops. Heaps are drawn with their top first.
2	L6	x=5 low.size=1 high.size=0	low.add(5). The new value always enters the lower half first.
3	L7	x=5 moved=5 low.size=0 high.size=1	high.add(low.poll()): the largest value of the lower half (5) moves up. This guarantees every low value is <= every high value.
4	L8	low.size=0 high.size=1	The upper half is bigger than the lower half, so rebalance.
5	L9	moved=5 low.size=1 high.size=0	Move 5 back to the lower half.
6	L14	median=5 low.size=1 high.size=0	Odd count: the median is the top of low, 5.
7	L6	x=15 low.size=2 high.size=0	low.add(15). The new value always enters the lower half first.
8	L7	x=15 moved=15 low.size=1 high.size=1	high.add(low.poll()): the largest value of the lower half (15) moves up. This guarantees every low value is <= every high value.
9	L8	low.size=1 high.size=1	Sizes are balanced: low is equal or one larger.
10	L14	median=10 low.size=1 high.size=1	Even count: the median is the average of the two tops, (5 + 15) / 2 = 10.
11	L6	x=1 low.size=2 high.size=1	low.add(1). The new value always enters the lower half first.
12	L7	x=1 moved=5 low.size=1 high.size=2	high.add(low.poll()): the largest value of the lower half (5) moves up. This guarantees every low value is <= every high value.
13	L8	low.size=1 high.size=2	The upper half is bigger than the lower half, so rebalance.
14	L9	moved=5 low.size=2 high.size=1	Move 5 back to the lower half.
15	L14	median=5 low.size=2 high.size=1	Odd count: the median is the top of low, 5.
16	L6	x=3 low.size=3 high.size=1	low.add(3). The new value always enters the lower half first.
17	L7	x=3 moved=5 low.size=2 high.size=2	high.add(low.poll()): the largest value of the lower half (5) moves up. This guarantees every low value is <= every high value.
18	L8	low.size=2 high.size=2	Sizes are balanced: low is equal or one larger.
19	L14	median=4 low.size=2 high.size=2	Even count: the median is the average of the two tops, (3 + 5) / 2 = 4.
20	L6	x=8 low.size=3 high.size=2	low.add(8). The new value always enters the lower half first.
21	L7	x=8 moved=8 low.size=2 high.size=3	high.add(low.poll()): the largest value of the lower half (8) moves up. This guarantees every low value is <= every high value.
22	L8	low.size=2 high.size=3	The upper half is bigger than the lower half, so rebalance.
23	L9	moved=5 low.size=3 high.size=2	Move 5 back to the lower half.
24	L14	median=5 low.size=3 high.size=2	Odd count: the median is the top of low, 5.
25	L6	x=7 low.size=4 high.size=2	low.add(7). The new value always enters the lower half first.
26	L7	x=7 moved=7 low.size=3 high.size=3	high.add(low.poll()): the largest value of the lower half (7) moves up. This guarantees every low value is <= every high value.
27	L8	low.size=3 high.size=3	Sizes are balanced: low is equal or one larger.
28	L14	median=6 low.size=3 high.size=3	Even count: the median is the average of the two tops, (5 + 7) / 2 = 6.
29	L6	x=9 low.size=4 high.size=3	low.add(9). The new value always enters the lower half first.
30	L7	x=9 moved=9 low.size=3 high.size=4	high.add(low.poll()): the largest value of the lower half (9) moves up. This guarantees every low value is <= every high value.
31	L8	low.size=3 high.size=4	The upper half is bigger than the lower half, so rebalance.
32	L9	moved=7 low.size=4 high.size=3	Move 7 back to the lower half.
33	L14	median=7 low.size=4 high.size=3	Odd count: the median is the top of low, 7.
34	L6	x=10 low.size=5 high.size=3	low.add(10). The new value always enters the lower half first.
35	L7	x=10 moved=10 low.size=4 high.size=4	high.add(low.poll()): the largest value of the lower half (10) moves up. This guarantees every low value is <= every high value.
36	L8	low.size=4 high.size=4	Sizes are balanced: low is equal or one larger.
37	L14	median=7.5 low.size=4 high.size=4	Even count: the median is the average of the two tops, (7 + 8) / 2 = 7.5.

Practice ladder

Now try it yourself

Easy

Kth Largest Element in a Stream
Find Median from Data Stream (small inputs)

Medium

Find Median from Data Stream
IPO

Advanced

Sliding Window Median
Maximize Capital with two heaps

Key takeaways

Keep the lower half in a max-heap and the upper half in a min-heap; the median is at the tops.
After every insertion move at most one top across to restore |lo| = |hi| or |lo| = |hi| + 1.
Lazy deletion marks values as stale and removes them only when they reach a top.
Prune a heap's top after any change that could expose a stale value.