# How to Use Heaps and Priority Queues for Median Finding in a Data Stream

> Find the median of a data stream efficiently using two heaps. Learn how heaps and priority queues enable O(log n) insertion and O(1) median retrieval for dynamic data.

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: how-to-guide
- Published: 2026-02-25

---

**Use two heaps—a max-heap for the lower half and a min-heap for the upper half—to maintain the median of a dynamic data stream with O(log n) insertion and O(1) retrieval.**

The `labuladong/fucking-algorithm` repository implements this classic algorithm in the `MedianFinder` class, demonstrating how priority queues efficiently solve the "Find Median from Data Stream" problem across C++, Java, and Go.

## The Two-Heap Algorithm for Dynamic Median Finding

The core strategy relies on partitioning the data stream into two halves using **heap data structures**:

- **`small` (max-heap)** – Stores the smaller half of the numbers. Its root contains the largest element of the lower half.
- **`large` (min-heap)** – Stores the larger half of the numbers. Its root contains the smallest element of the upper half.

By maintaining the **size invariant**—where the heaps differ in size by at most one element—you guarantee immediate access to the median:

- If one heap contains more elements, its top element is the median.
- If both heaps have equal size, the median is the average of both tops.

Insertions follow a **rebalancing protocol**: push the new value into the appropriate heap, then move the top element from the larger heap to the smaller one if the size difference exceeds one. This ensures both **O(log n)** insertion complexity and **O(1)** median retrieval.

## Implementation Details in labuladong/fucking-algorithm

The repository provides complete implementations in `多语言解法代码/solution_code.md`, with language-specific variations that preserve the identical algorithmic skeleton.

### C++ Implementation (Lines 24901–24927)

In the C++ version, `priority_queue<int>` serves as the max-heap for the lower half, while `priority_queue<int, vector<int>, greater<int>>` implements the min-heap for the upper half:

```cpp
class MedianFinder {
private:
    priority_queue<int> large;                              // max-heap for lower half
    priority_queue<int, vector<int>, greater<int>> small;   // min-heap for upper half
public:
    void addNum(int num) {
        if (small.size() >= large.size()) {
            small.push(num);
            large.push(small.top());
            small.pop();
        } else {
            large.push(num);
            small.push(large.top());
            large.pop();
        }
    }
    double findMedian() {
        if (large.size() < small.size()) return small.top();
        if (large.size() > small.size()) return large.top();
        return (large.top() + small.top()) / 2.0;
    }
};

```

Note that the C++ implementation uses `large` for the max-heap (lower half) and `small` for the min-heap (upper half), which reverses the typical naming convention but maintains the correct logic.

### Java Implementation (Lines 25152–25178)

The Java version uses `PriorityQueue` with a custom comparator `(a, b) -> b - a` to create the max-heap for the lower half, while the default `PriorityQueue` serves as the min-heap for the upper half:

```java
class MedianFinder {
    private PriorityQueue<Integer> large; // min-heap for upper half
    private PriorityQueue<Integer> small; // max-heap for lower half (custom comparator)

    public MedianFinder() {
        large = new PriorityQueue<>();
        small = new PriorityQueue<>((a, b) -> b - a);
    }

    public void addNum(int num) {
        if (small.size() >= large.size()) {
            small.offer(num);
            large.offer(small.poll());
        } else {
            large.offer(num);
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        if (large.size() < small.size()) return small.peek();
        if (large.size() > small.size()) return large.peek();
        return (large.peek() + small.peek()) / 2.0;
    }
}

```

### Go Implementation (Lines 24445–25030)

The Go implementation defines custom types `PriorityQueue` and `ReversePriorityQueue` to wrap the standard `container/heap` interface, providing min-heap and max-heap functionality respectively:

```go
type MedianFinder struct {
    large *PriorityQueue        // min-heap for upper half
    small *ReversePriorityQueue // max-heap for lower half
}

func Constructor() MedianFinder {
    return MedianFinder{
        large: &PriorityQueue{},
        small: &ReversePriorityQueue{},
    }
}

func (this *MedianFinder) AddNum(num int) {
    if this.small.Len() >= this.large.Len() {
        this.small.Push(num)
        heap.Push(this.large, this.small.Pop())
    } else {
        this.large.Push(num)
        heap.Push(this.small, this.large.Pop())
    }
}

func (this *MedianFinder) FindMedian() float64 {
    if this.large.Len() < this.small.Len() {
        return float64(this.small.Top())
    }
    if this.large.Len() > this.small.Len() {
        return float64(this.large.Top())
    }
    return (float64(this.large.Top()) + float64(this.small.Top())) / 2.0
}

```

## How the MedianFinder Class Works

The `MedianFinder` class exposed in [`solution_code.md`](https://github.com/labuladong/fucking-algorithm/blob/main/solution_code.md) abstracts the two-heap logic into two public operations:

### addNum(num)

When a new integer arrives, the method determines which heap receives the value based on current sizes. If the **max-heap** (lower half) has equal or greater size, the new element initially enters the lower half, then the largest element of the lower half moves to the upper half to maintain balance. Otherwise, the reverse occurs. This rebalancing guarantees that the size difference between heaps never exceeds one.

### findMedian()

Retrieval operates in constant time by comparing heap sizes:
- If the **max-heap** (lower half) contains more elements, its root (the largest of the smaller half) is the median.
- If the **min-heap** (upper half) contains more elements, its root (the smallest of the larger half) is the median.
- If sizes are equal, the median is the average of both roots.

This approach yields **O(log n)** insertion and **O(1)** query complexity, significantly outperforming sorting or array-based methods for streaming data.

## Summary

- **Two-heap technique** is the standard method for maintaining a running median using **heaps and priority queues for median finding** in dynamic data streams.
- The `labuladong/fucking-algorithm` repository implements this in the `MedianFinder` class across C++, Java, and Go in `多语言解法代码/solution_code.md`.
- **Max-heap** stores the smaller half of numbers, **min-heap** stores the larger half, with sizes balanced to differ by at most one.
- **Time complexity**: O(log n) for `addNum` and O(1) for `findMedian`.
- Supporting documentation appears in [`README.md`](https://github.com/labuladong/fucking-algorithm/blob/main/README.md) (line 265) and `数据结构系列/BST1.md` (lines 113-115).

## Frequently Asked Questions

### Why use two heaps instead of sorting?

Sorting requires O(n log n) time per insertion or periodic re-sorting of the entire dataset. The two-heap approach maintains the median with O(log n) per insertion by only moving elements between the two heap tops, avoiding full array scans or reordering.

### What is the time complexity of the two-heap median finder?

Insertion via `addNum` runs in **O(log n)** time because each push and pop operation on a binary heap costs logarithmic time, and we perform a constant number of such operations. Retrieval via `findMedian` runs in **O(1)** time because it only inspects the top elements of the heaps.

### How does the heap rebalancing work?

When inserting a new number, you first place it in the appropriate heap (typically the max-heap for the lower half). If the size difference between the two heaps exceeds one, you move the root element from the larger heap to the smaller one. This ensures the max-heap always contains the largest elements of the lower half and the min-heap contains the smallest elements of the upper half.

### Where can I find the original implementation?

The complete implementations are located in `多语言解法代码/solution_code.md` within the `labuladong/fucking-algorithm` repository. Specifically, the C++ version appears at lines 24901–24927, the Java version at lines 25152–25178, and the Go version at lines 24445–25030. Additional theoretical background is available in [`README.md`](https://github.com/labuladong/fucking-algorithm/blob/main/README.md) (line 265) and `数据结构系列/BST1.md` (lines 113–115).