Two Heaps Pattern: Find the Median of a Data Stream Without Sorting

Scenario context

Two Heaps partitions a stream into two sorted halves. A max-heap holds everything below the median; a min-heap holds everything above it. Keep the heaps size-balanced and you can read the median from either top in O(1) — no sorting needed, ever.

Spotify processes millions of salary records and wants to display the median compensation in real time as each new record arrives. The naive approach — collect all rec…

This walkthrough focuses on The Real-Time Median Problem: Why Sorting the Whole Stream Fails.

Before making a design choice, clarify:

• Spotify processes millions of salary records and wants to display the median compensation in real time as each new record arrives.
• The naive approach — collect all records, sort them, pick the middle — has two fatal flaws: sorting is O(N log N) and you would have to re-sort after every single insertion.
• The Two Heaps pattern eliminates this waste by keeping the data permanently organized around a single invariant: the entire lower half of the data set lives in one heap, and the entire upper half lives in another.

Concepts in play: tree-data-structures, jvm-internals-and-garbage-collection, core-algorithm-patterns, database-indexing

Stage 1 — Max-Heap and Min-Heap: Partitioning a Stream into Two Halves

• A max-heap always exposes its largest element at the top.
• A min-heap always exposes its smallest element at the top.
• These two properties are exactly what you need to see the boundary between "smaller than median" and "larger than median" without scanning the collection.
• Here is the core insight spelled out plainly: - Put every number less than or equal to the current median in the max-heap .

import java.util.Collections;
import java.util.PriorityQueue;

// Max-heap: lower half of the stream
PriorityQueue<Integer> lowerHalf = new PriorityQueue<>(Collections.reverseOrder());

// Min-heap: upper half of the stream
PriorityQueue<Integer> upperHalf = new PriorityQueue<>();

Observable outcome: Here is the core insight spelled out plainly: - Put every number less than or equal to the current median in the max-heap .

Stage 2 — The Balancing Rule: Keeping the Two Heaps in Sync

• After every insertion, the heap sizes must satisfy this invariant: lowerHalf.size() - upperHalf.size() is always 0 or 1.
• When both heaps have equal size, the median is the average of their tops.
• When the lower half has one extra element, the median is lowerHalf.peek() .
• Push the new number into lowerHalf (max-heap).

Observable outcome: Push the new number into lowerHalf (max-heap).

Stage 3 — Deep Dive: How Java's PriorityQueue Implements the Two Halves

• Internals: PriorityQueue Memory Layout and the Max-Heap Trick Java's PriorityQueue is a binary heap stored in a flat array .
• For a min-heap of size N, the element at index i is always less than or equal to both children at indices 2i+1 and 2i+2 .
• The root (index 0) is always the minimum — peek() returns it in O(1) by simply reading queue[0] .
• offer(x) appends the new element at the end of the array and then sifts up : it swaps the element with its parent repeatedly until the heap property is satisfied.

Observable outcome: offer(x) appends the new element at the end of the array and then sifts up : it swaps the element with its parent repeatedly until the heap property is satisfied.

Stage 4 — Watching Seven Numbers Flow through Two Heaps

• After inserting the stream [5, 10, 1, 7, 3, 8, 4], the two heaps stabilize to this configuration.
• The lower half max-heap holds [5, 4, 3, 1] and the upper half min-heap holds [7, 8, 10]: The insertion flowchart, applied once for each arriving element: The diagram shows why the rebalance step in D is the only conditi…
• The two-move insertion (B → C) always runs; the rebalance (E) only fires when the upper half has grown too large.

graph TD
    subgraph lower["Lower Half  Max-Heap  (top = 5)"]
        L1[5] --> L2[4]
        L1 --> L3[3]
        L2 --> L4[1]
    end
    subgraph upper["Upper Half  Min-Heap  (top = 7)"]
        U1[7] --> U2[8]
        U1 --> U3[10]
    end
    L1 -. "Median = (5 + 7) / 2.0 = 6.0" .-> U1

flowchart TD
    A([New number arrives]) --> B[Push to lowerHalf max-heap]
    B --> C[Pop lowerHalf top  push to upperHalf]
    C --> D{upperHalf.size > lowerHalf.size?}
    D -- Yes --> E[Pop upperHalf top  push to lowerHalf]
    D -- No --> F{Total count is odd?}
    E --> F
    F -- Yes --> G["findMedian() = lowerHalf.peek()"]
    F -- No --> H["findMedian() = (lowerHalf.peek() + upperHalf.peek()) / 2.0"]

Observable outcome: The two-move insertion (B → C) always runs; the rebalance (E) only fires when the upper half has grown too large.

Stage 5 — Real-World Uses: Salary Analytics, Sliding Windows, and Capital Allocation

• The Two Heaps pattern solves a surprisingly wide class of problems because "median of a growing or sliding data set" appears in many systems: Streaming analytics platforms — Compensation analysis tools at Spotify, Linke…
• Re-sorting the entire list after each update is impractical at millions of records.
• Two Heaps reduces each update to O(log N) regardless of total size.
• Network latency monitoring — Observability stacks like Prometheus track P50 (median) request latency over rolling time windows.

Observable outcome: Network latency monitoring — Observability stacks like Prometheus track P50 (median) request latency over rolling time windows.

End-to-end outcome

After working through the stages, you should be able to explain:

• • Core idea: Partition the stream into a max-heap (lower half) and a min-heap (upper half), keeping them size-balanced.
• The median is always at one or both tops.

Alternatives considered

Decision Guide: Choosing Between Two Heaps and Its Alternatives

Decision Guide: Choosing Between Two Heaps and Its Alternatives

Java PriorityQueue vs. TreeMap: Alternative Implementations

Java's PriorityQueue is the standard choice and handles most Two Heaps problems in O(log N) per operation.

Failure and degraded modes

Trade-offs: When Two Heaps Shine and When They Hurt

• Detection: Two Heaps gives you the best possible median query time (O(1)) at the cost of O(log N) inserts and O(N) deletions.
• User or operator impact: Two Heaps gives you the best possible median query time (O(1)) at the cost of O(log N) inserts and O(N) deletions.

Lessons Learned: Common Two Heaps Pitfalls in Interviews

• Detection: Forgetting the two-step insert.
• User or operator impact: Forgetting the two-step insert.