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

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:

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:

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:

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 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 (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 (line 265) and 数据结构系列/BST1.md (lines 113–115).

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}