0295-find-median-from-data-stream.cs

publicclassMedianFinder{
privatePriorityQueue<int,int>leftHeap=new(Comparer<int>.Create((a,b)=>b-a));
privatePriorityQueue<int,int>rightHeap=new();

publicMedianFinder(){

}

// T: log(n)
publicvoidAddNum(intnum){
if(leftHeap.Count==0||num>leftHeap.Peek())
rightHeap.Enqueue(num,num);
else
leftHeap.Enqueue(num,num);

Balance();
}

privatevoidBalance(){
var(big,small)=leftHeap.Count>rightHeap.Count
?(leftHeap,rightHeap)
:(rightHeap,leftHeap);

while(big.Count-small.Count>1){
varvalue=big.Dequeue();
small.Enqueue(value,value);
}
}

// T: O(1)
publicdoubleFindMedian(){
if(leftHeap.Count==rightHeap.Count)
return(leftHeap.Peek()+rightHeap.Peek())/2.0;

returnleftHeap.Count>rightHeap.Count
?leftHeap.Peek()
:rightHeap.Peek();
}
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.AddNum(num);
 * double param_2 = obj.FindMedian();
 */