The Middle Ground
How do you find the Median of a continuously growing stream of numbers?
[2]→ Median 2[2, 3]→ Median 2.5[2, 3, 4]→ Median 3
Sorting every time is too slow (O(N log N)).
1. The Two Heaps Pattern
Split the data into two halves:
- Small Half: Max Heap (We need the largest of the smalls).
- Large Half: Min Heap (We need the smallest of the large).
Median is either the top of one heap or the average of both tops.
2. Interactive: Two Heaps
Add numbers. See them balance.
Max Heap (Small)
Min Heap (Large)
Median: 0
3. Implementation
Java
Go
```java
class MedianFinder {
PriorityQueue small = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue large = new PriorityQueue<>();
public void addNum(int num) {
small.offer(num);
large.offer(small.poll());
if (large.size() > small.size()) {
small.offer(large.poll());
}
}
public double findMedian() {
if (small.size() > large.size()) return small.peek();
return (small.peek() + large.peek()) / 2.0;
}
}
```
</div>
```go
import "container/heap"
// IntHeap is a basic Min-Heap
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
// MaxHeap overrides Less
type MaxHeap struct { IntHeap }
func (h MaxHeap) Less(i, j int) bool { return h.IntHeap[i] > h.IntHeap[j] }
type MedianFinder struct {
small *MaxHeap
large *IntHeap
}
func Constructor() MedianFinder {
return MedianFinder{
small: &MaxHeap{},
large: &IntHeap{},
}
}
func (this *MedianFinder) AddNum(num int) {
heap.Push(this.small, num)
heap.Push(this.large, heap.Pop(this.small).(int))
if this.large.Len() > this.small.Len() {
heap.Push(this.small, heap.Pop(this.large).(int))
}
}
func (this *MedianFinder) FindMedian() float64 {
if this.small.Len() > this.large.Len() {
return float64((*this.small).IntHeap[0])
}
return float64((*this.small).IntHeap[0] + (*this.large)[0]) / 2.0
}
```
</div>