입력 데이타가 스트림으로 계속 들어오기 때문에, 미리 전체 입력 자료의 수를 알 수 없다. 따라서 입력을 해가면서 중간값 상태를 계속 유지할 필요가 있다. 중간값을 구하기 위해서 현재까지 입력된 데이타를 2개의 서브셋으로 나눌 수 있다. 만약 전체 입력 수가 짝수라면, 두 서브셋의 갯수는 동일하며, 첫 서브셋의 최대값과 두번째 서브셋의 최소값이 중간값을 구하는데 사용될 수 있다. 만약 입력 수가 홀수라면, 두 서브셋중 하나(최대 혹은 최소)에서 중간값을 구할 수 있다. 이러한 서브셋을 구현하기 위해 MaxHeap과 MinHeap을 사용할 수 있는데, 이는 Heap이 정렬되지 않은 집합에서도 항상 최대 혹은 최소를 즉시 (O(1)) 구할 수 있는 장점을 이용할 수 있기 때문이다.

연속적인 데이타라는 특성을 반영하기 위해서 maxheap, minheap을 private field로 두고 데이타를 입력받는 메서드와 특정 싯점에 중간값을 출력하는 메서드를 아래와 같이 생각해 볼 수 있다. (MaxHeap, MinHeap은 힙 자료구조(http://www.csharpstudy.com/DS/heap.aspx) 예제 참조)

class Median
{
    private MaxHeap maxHeap = new MaxHeap();
    private MinHeap minHeap = new MinHeap();   

    public void AddValue(int num)
    {
        if (minHeap.Count == maxHeap.Count)
        {
            if (minHeap.Count > 0 && maxHeap.Peek() > num)
            {
                minHeap.Add(maxHeap.RemoveOne());
                maxHeap.Add(num);
            }
            else
                minHeap.Add(num);
        }
        else //같지 않으면 minheap이 1개 많음
        {
            if (minHeap.Peek() < num)
            {
                maxHeap.Add(minHeap.RemoveOne());
                minHeap.Add(num);
            }
            else
            {
                maxHeap.Add(num);
            }
        }
    }

    public int GetMedian()
    {
        if (maxHeap.Count == minHeap.Count)
            return (maxHeap.Peek() + minHeap.Peek()) / 2;
        else
            return minHeap.Peek();
    }
}

// 테스트
var m = new Median();
for (int i = 1; i <= 10; i++)  m.AddValue(i);
Console.WriteLine(m.GetMedian());
for (int i = 11; i <= 20; i++)  m.AddValue(i);
Console.WriteLine(m.GetMedian());