Median Using Two Heaps: Data Structure Pattern

Split the numbers in half: a max-heap holds the smaller half (its top = biggest small), a min-heap holds the bigger half (top = smallest big). The median lives at the boundary.

“Median in a stream / running median / sliding median” → two heaps

Pattern: Add + Median

The stream marches left to right; the two heaps trade elements to stay balanced. Press ▶.

Find Median from Data Stream

Median in a stream / running median → two heaps. Split the data into two halves: a max-heap for the smaller half, a min-heap for the larger. The median lives at the boundary between the two roots.

Stream: [5,15,1,3]. We maintain two heaps: a max-heap (lower half) and a min-heap (upper half). Each new element is added to the appropriate heap, then we rebalance so sizes differ by at most 1. The median is always derivable from the two roots.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        add(x):
                      
                        2
                          if x <= top(lower): push(lower, x)   # max-heap
                      
                        3
                          else:              push(upper, x)    # min-heap
                      
                        4
                          # rebalance: sizes differ by ≤ 1 (lower may lead by 1)
                      
                        5
                        median():
                      
                        6
                          odd n → top(lower); even n → avg(top(lower), top(upper))

PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max
PriorityQueue<Integer> upper = new PriorityQueue<>();                            // min

public void add(int x) {
    if (lower.isEmpty() || x <= lower.peek()) lower.offer(x);
    else                                      upper.offer(x);

    // rebalance: sizes differ by at most 1, lower may lead
    if (lower.size() > upper.size() + 1)
        upper.offer(lower.poll());
    else if (upper.size() > lower.size())
        lower.offer(upper.poll());
}

public double median() {
    if (lower.size() > upper.size()) return lower.peek();
    return (lower.peek() + upper.peek()) / 2.0;
}

import heapq

lower, upper = [], []   # negated max-heap, min-heap

def add(x):
    if not lower or x <= -lower[0]:
        heapq.heappush(lower, -x)
    else:
        heapq.heappush(upper, x)

    if len(lower) > len(upper) + 1:
        heapq.heappush(upper, -heapq.heappop(lower))
    elif len(upper) > len(lower):
        heapq.heappush(lower, -heapq.heappop(upper))

def median():
    if len(lower) > len(upper):
        return -lower[0]
    return (-lower[0] + upper[0]) / 2

priority_queue<int> lower;                        // max
priority_queue<int, vector<int>, greater<int>> upper; // min

void add(int x) {
    if (lower.empty() || x <= lower.top()) lower.push(x);
    else                                   upper.push(x);

    if (lower.size() > upper.size() + 1) { upper.push(lower.top()); lower.pop(); }
    else if (upper.size() > lower.size()) { lower.push(upper.top()); upper.pop(); }
}

double median() {
    if (lower.size() > upper.size()) return lower.top();
    return (lower.top() + upper.top()) / 2.0;
}

const lower = new MaxHeap(); // smaller half
const upper = new MinHeap(); // larger half

function add(x) {
  if (!lower.size() || x <= lower.peek()) lower.push(x);
  else upper.push(x);

  if (lower.size() > upper.size() + 1) upper.push(lower.pop());
  else if (upper.size() > lower.size()) lower.push(upper.pop());
}

function median() {
  if (lower.size() > upper.size()) return lower.peek();
  return (lower.peek() + upper.peek()) / 2;
}

Median = the wall between the halves. Keep the walls’ tops handy and rebalance after every insert.

Common Mistakes

Both heaps the same type (need one MAX + one MIN).
Letting sizes drift past ±1 — median then reads the wrong heap.
Python: forgetting to negate values pushed into lower.
Integer division when averaging (/ 2.0, not / 2).

Complexity

Operation	Time
add	O(log n)
median	O(1)
Space	O(n)

⚠️ Animation & Content Notice

Median with Two Heaps

Pattern: Add + Median

⚠️ Animation & Content Notice

Find Median from Data Stream

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Pattern: Add + Median

Find Median from Data Stream

Common Mistakes

Complexity

Premium Content

My Private Notes