Find the median of a data stream?

public class MedianFinder {
private PriorityQueue<int, int> maxHeap; // lower half (max

heap)

Follow on:

private PriorityQueue<int, int> minHeap; // upper half (min

heap)

public MedianFinder() {

maxHeap = new PriorityQueue<int,

int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
minHeap = new PriorityQueue<int, int>();
}
public void AddNum(int num) {

maxHeap.Enqueue(num, num);

minHeap.Enqueue(maxHeap.Dequeue(), maxHeap.Peek());

if (maxHeap.Count < minHeap.Count)

maxHeap.Enqueue(minHeap.Dequeue(), minHeap.Peek());

}
public double FindMedian() {
if (maxHeap.Count > minHeap.Count)
return maxHeap.Peek();
return (maxHeap.Peek() + minHeap.Peek()) / 2.0;
}
}

Explanation:

Maintain two heaps: maxHeap for lower half, minHeap for upper half. Balance their sizes.