advanced9 min read·Updated September 30, 2026

Median from a Data Stream Explained: Tracking 1 to 5 with Heaps

Master the two-heap pattern for streaming medians. Walk through inserting 1 through 5 step-by-step with mental models, invariants, and edge cases.

By Learnisim AI·Published September 30, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Min-heap and Max-heap data structures
  • Basic array partitioning and balancing
Median from Data Stream: Two-Heap Architecture Stream: [1, 2, 3, 4, 5] — Insert: O(log n) | Median lookup: O(1) Incoming Stream: 1 2 3 4 5 → Medians: [1, 1.5, 2, 2.5, 3] Core Architecture: Two Heaps Partitioning Stream LOW (Max-Heap) Stores smaller half | root = max 2 root (mid if odd) 1 — Invariant: |low| == |high| or +1 Max size rule enforced HIGH (Min-Heap) Stores larger half | root = min 3 root (part of even avg) 4 5 Value Invariant: max(low) <= min(high) Cross-heap ordering Trace: Inserting [1, 2, 3, 4, 5] • Insert 1: low={1}, high={} → Med: 1 • Insert 2: low={1}, high={2} → Med: 1.5 • Insert 3: low={1,2}, high={3} → Med: 2 • Insert 4: low={2}, high={3,4}... → Med: 2.5 • Insert 5: low={2,3}, high={4,5} → Med: 3 Why Sorting Every Arrival Fails • Naive dynamic array sorting takes O(n) or O(n log n) • Millions of ticks/sec cause catastrophic latency spikes • Two heaps reduce lookup to instant O(1)!
Stream 1, 2, 3, 4, 5 — median after each insert overview diagram
Why

Why Sorting Every Arrival Fails at Scale

Phase 1: The Streaming Median Challenge

Imagine you are building a real-time analytics engine processing stock ticks, IoT sensor readings, or live financial logs. Your system receives numbers one by one in an unending stream. The business requirement is simple yet demanding: after every single incoming number, compute the exact median instantly.
Let us ground this in our locked working example. Our input stream arrives sequentially: 1, then 2, 3, 4, and finally 5. We need to report the median after each insert:
•After inserting 1: median is 1
•After inserting 2: median is 1.5
•After inserting 3: median is 2
•After inserting 4: median is 2.5
•After inserting 5: median is 3
If you reach for the most intuitive naive approach, you might keep a growing list in memory, insert each incoming item, and sort the entire dataset from scratch to find the middle element. For total elements, keeping a dynamic array sorted takes time per insertion using linear search or using full re-sorting. When reaches millions of data points per second, pausing to sort the entire history on every single insert introduces catastrophic latency spikes. We need a way to maintain our ordering invariant without sorting the whole collection every time a new number arrives.
Median From a Data Stream: Why Sorting Every Arrival Fails at Scale Naive Approach: Dynamic Array + Full Sort Insert incoming element into array, then re-sort entire history. Takes O(n log n) per insert! 1 2 3 4 5 Catastrophic Latency Spikes at Scale! O(N) Re-sort Concrete Worked Example: Incoming Stream & Resulting Median Arrival: [1] Median: 1 Arrival: [1, 2] Median: 1.5 Arrival: [1, 2, 3] Median: 2 Arrival: [1, 2, 3, 4] Median: 2.5 Arrival: [1, 2, 3, 4, 5] Median: 3 Optimal Solution: Two Heaps (O(1) Median Access, O(log N) Insert) Split stream into two halves: Max-Heap for lower half, Min-Heap for upper half. Roots always give us the median instantly! Max-Heap (Lower Half) Max Root = Median for even size 2 1 ___ O(1) Peek MEDIAN Min-Heap (Upper Half) Min Root = Median for even size 3 4 5
Why Sorting Every Arrival Fails at Scale diagram
Model

Two Heaps Partitioning the Stream

Phase 2: The Two-Heap Architecture

To find the median after every insert without sorting the entire dataset, we need a data structure that exposes the middle elements in time while allowing fast insertions. The core mental model for Median from a data stream (two heaps) explained relies on splitting our incoming stream—such as our working example of 1, 2, 3, 4, 5—into two symmetrical halves.
Imagine a seesaw balancing our data. We maintain two priority queues:
* A max-heap (let's call it low) that stores the smaller half of the numbers seen so far, with the largest of those small numbers sitting right at the root.
* A min-heap (let's call it high) that stores the larger half of the numbers seen so far, with the smallest of those large numbers sitting right at the root.
If we enforce two structural invariants after every insertion, the median becomes trivial to read:
1. Value Invariant: Every number in low must be less than or equal to every number in high. In other words, low.top() <= high.top().
2. Size Invariant: The sizes of the two heaps must remain balanced. Specifically, the number of elements in low must equal the number of elements in high, or exceed it by at most one (0 <= |low| - |high| <= 1).
When these invariants hold, finding the median is a deterministic lookups operation:
* If the total number of elements is odd (|low| > |high|), the median is simply the root of the low max-heap.
* If the total number of elements is even (|low| == |high|), the median is the average of the low max-heap root and the high min-heap root.
For instance, as we stream 1, 2, 3, 4, 5, every new arrival is first routed into low, re-balanced via heap pops and pushes to satisfy our two invariants, and leaves us ready to extract the median in constant time.
Median from a Data Stream (Two Heaps Partitioning) Example stream: [1, 2, 3, 4, 5] — O(1) Median Lookup via Size & Value Invariants Incoming Stream: 1 2 3 4 5 → inserted one by one into heaps with re-balancing Size Balanced (|Low| == |High| or |Low| = |High| + 1) LOW (Max-Heap: Smaller Half) 2 1 3 (stream peak) Root gives max of lower half (O(1) access) Contains elements: {1, 2, 3} HIGH (Min-Heap: Larger Half) 4 5 (balanced size) Root gives min of upper half (O(1) access) Contains elements: {4, 5} MEDIAN RESULT Root(Low) = 3 Value Invariant: max(Low) ≤ min(High) (i.e., 3 ≤ 4) • Odd count → Low.root() is median
Two Heaps Partitioning the Stream diagram
Worked example

Tracing the Two Heaps: Inserting 1, 2, 3, 4, and 5

Phase 3: Worked Example

To see how the two-heap architecture operates in practice, let's trace our stream: . We maintain two heaps: a max-heap called low for the lower half of the numbers, and a min-heap called high for the upper half.
Given:
- low (max-heap): initially empty
- high (min-heap): initially empty
- Invariants: low.size() == high.size() or low.size() == high.size() + 1, and every element in low is every element in high.
Steps:
1.Insert 1:

- Push 1 into low. Sizes are low = , high = .
- Balance check: low size is 1, high size is 0. Difference is 1 (valid).
- Result: Median is low.top(), which is 1.
2.Insert 2:

- Push 2 into low (or high depending on your convention; let's push to low first, giving in low, then rebalance by popping max of low (2) and pushing to high).
- low = , high = . Sizes are equal ().
- Result: Count is even (2). Median = average of low.top() (1) and high.top() (2), yielding 1.5.
3.Insert 3:

- Push 3 into low. low becomes , high = .
- Rebalance: low max is 3, push to high. Now low = , high = . Sizes: low = 1, high = 2. Violates low.size() >= high.size(). Move high.min() (2) back to low.
- Final states: low = , high = .
- Result: Count is odd (3). Median = low.top(), which is 2.
4.Insert 4:

- Push 4 into low. low becomes , high = .
- Rebalance: Move max of low (4) to high. low = , high = . Sizes: low = 2, high = 2.
•Result: Count is even (4). Median = average of 2 and 3, yielding 2.5.
5.Insert 5:

- Push 5 into low. low = , high = .
- Rebalance: Move max of low (5) to high. high becomes , low = . Sizes: low = 2, high = 3 (violates size invariant).
- Move min of high (3) to low. low = , high = .
- Result: Count is odd (5). Median = low.top(), which is 3.
python
import heapq

class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap (stored as negative numbers in Python)
        self.high = []  # min-heap

def addNum(self, num: int) -> None:
        # TODO: Implement insertion and balancing for the next step
        pass

def findMedian(self) -> float:
        # TODO: Return correct median based on heap sizes
        pass
Tracing the Two Heaps: Inserting 1, 2, 3, 4, 5 Stream walkthrough showing partition into Max-Heap (low) and Min-Heap (high) STREAM: 1 2 3 4 5 ← Final State after 5 LOW (Max-Heap) Stores lower half of stream (max at top) 3 .top() 1 2 Elements: {1, 2, 3} (size = 3) HIGH (Min-Heap) Stores upper half of stream (min at top) 4 .top() 5 Elements: {4, 5} (size = 2) AFTER INSERTING 5 (Odd Count: 5) Median = low.top() = 3 size(low) == size(high) + 1
Tracing the Two Heaps: Inserting 1, 2, 3, 4, and 5 diagram
Practice

Predicting Heap States for a Decreasing Stream

Phase 4: Practice

Now that you have traced the standard ascending stream , let us test how your heap balance invariant holds up when the data order flips.
Imagine you feed a strictly decreasing stream: into our two-heap architecture. In the previous worked example, numbers arrived from smallest to largest, causing the max-heap (low) to fill up first during initial pushes. With a descending stream, every new arrival is smaller than what is already stored, forcing your rebalancing logic to continually shift elements between low and high.
Work through the first three insertions mentally using our balance rules:
1. Insert 5: goes to low. (low: , high: )
2. Insert 4: goes to low, then balance check kicks in because sizes or max/min rules shift.
3.Insert 3: evaluate where 3 lands relative to the current heap roots.
Can you predict the exact contents of low (max-heap) and high (min-heap) after the third element (3) is fully inserted and balanced?
Apply

Extending Two Heaps to Sliding Window Median

Phase 5: Applying the Two-Heap Paradigm Beyond Static Streams

Now that you have mastered inserting into our running stream , consider a common production constraint: what happens when your data stream is unbounded, but you only care about the median of the last elements? This is the classic sliding window median problem, where elements both enter from the right and expire from the left.
In our base example, every element we inserted stayed forever. In a sliding window of size , when 4 arrives, 1 must leave. If 1 happens to sit deep inside our max-heap or min-heap, we cannot simply pop it in time. Standard heaps do not support arbitrary element removal in logarithmic time without expensive index tracking.
The transfer of our mental model requires adding lazy deletion. Instead of purging an expired element immediately, we record its expiration in a hash map of delayed counts. When that element eventually floats to the top of low or high, our balance and median-retrieval routines check the map and discard it on sight.
python
# Conceptual transfer: handling stale elements at the heap root
def clean_tops(low, high, delayed):
    while low.top() in delayed:
        delayed[low.top()] -= 1
        low.pop()
By combining our balanced dual-heap invariant with a lazy-deletion map, the per-operation performance guarantee survives even when elements vanish from the active window.
python
class SlidingWindowMedian:
    def __init__(self, k: int):
        self.k = k
        self.low = []   # max-heap via negated values
        self.high = []  # min-heap
        self.delayed = {}

# Question: Explain how the balance invariant (|low| - |high| in {0, 1})
    # must be adjusted or re-checked after cleaning stale tops from delayed.

FAQ

What is the median after inserting 4 into the stream [1, 2, 3] using two heaps?
After inserting 4, the max-heap holds [1, 2] and the min-heap holds [3, 4]. Since the total count (4) is even, the median is the average of the two roots (2 and 3), resulting in 2.5.
Why do we use two heaps instead of sorting the stream?
Sorting every time a new element arrives takes O(N log N) or O(N) per insertion. Two heaps (a max-heap and a min-heap) allow O(log N) insertions and O(1) median retrieval.
How do you handle heap balancing when sizes differ?
The max-heap and min-heap sizes must differ by at most one. If one heap exceeds this balance after an insertion, the root of the larger heap is popped and pushed into the smaller heap.
What are the time and space complexities of the two-heap median approach?
Finding the median takes O(1) time. Inserting a new number takes O(log N) time due to heap rebalancing. Space complexity is O(N) to store all elements across both heaps.

Keep learning