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.