The Two Heaps pattern is used for:

• Finding the median in a dynamic stream of numbers
• Balancing two halves of a dataset
• Efficiently managing order statistics

This pattern is frequently used in sliding window, online median, and kth element problems.

Concept

The idea is to split the data into two parts:

• Max Heap (left): Keeps track of the smaller half of numbers. The root is the largest of the smaller numbers.
• Min Heap (right): Keeps track of the larger half of numbers. The root is the smallest of the larger numbers.

This way, the median (or approximate middle) can be found efficiently.

• If the total number of elements is even, the median is the average of the roots.
• If it's odd, the heap with more elements holds the median.

Compare to sorted array adding elements, maintaining sorted property takes O(n) shifting, but two heap takes O(log n) time.

func findMedian() float64 {
    if maxHeap.Len() == minHeap.Len() {
        return float64(maxHeap.Top()+minHeap.Top()) / 2
    }
    if maxHeap.Len() < minHeap.Len() {
	    return float64(minHeap.Top())
    }
    return float64(maxHeap.Top())
}

How to Balance Two Heaps?

func addNum(num int) {
    if maxHeap.Len() == 0 || num <= maxHeap.Top() {
        heap.Push(maxHeap, num)
    } else {
        heap.Push(minHeap, num)
    }

    // Rebalance
    if maxHeap.Len() > minHeap.Len()+1 {
        heap.Push(minHeap, heap.Pop(maxHeap))
    } else if maxHeap.Len()+1 < minHeap.Len() {
        heap.Push(maxHeap, heap.Pop(minHeap))
    }
}

⭐️ (Hard) 295. Find Median from Data Stream, NeetCode 75

https://leetcode.com/problems/find-median-from-data-stream

Last review: Sep 13, 2025 Next review: You understood the broad concept, but you struggled with details.

Similar Questions: