## Median from data stream

This video explains how to find median in a data stream.In this problem, given a stream of integers we are required to find median at any given point in a running integer also known as stream of integers.I have explained the problem with intuitive examples and i have also shown all the required intuition for solving the problem.I have first solved it using simple solution using sorting technique which is insertion sort.Later, I have shown the intuition for optimization and solved using 2 heaps. One maxheap containing left half values and the other as minheap containing the right half values of the ordered array.We can find median in constant time using the formula as I have shown for ODD and EVEN number of elements.

## CODE

```class MedianFinder {
public:
priority_queue<int> maxheap; //1st half (left half)
priority_queue<int,vector<int>,greater<int>> minheap; //2nd half (Right half)
/** initialize your data structure here. */
MedianFinder() {

}

int lsize = maxheap.size();
int rsize = minheap.size();
if(lsize==0)    //num is the 1st element in stream
maxheap.push(num);
else if(lsize==rsize)   //Push one element in maxheap for sure
{
if(num<minheap.top())   //num can be pushed to maxheap (1st half) to maintain order
maxheap.push(num);
else    //Push root of minheap to maxheap (Push num to 2nd half)
{
int temp = minheap.top();   //Save root of minheap
minheap.pop();  //Pop the root from minheap
minheap.push(num);  //Push num in minheap
maxheap.push(temp); //Push the previous saved root of minheap in the maxheap
}
}
else    ///We assume that maxheap can be larger than minheap by a max of 1 element only
{
if(minheap.size()==0)
{
if(num>maxheap.top()) //Push num to 2nd half
minheap.push(num);
else //Push num to 1st half
{
int temp = maxheap.top();
maxheap.pop();
maxheap.push(num);
minheap.push(temp);
}
}
else if(num>=minheap.top()) //Push the element directly in minheap (2nd half)
minheap.push(num);
else    //Push root of maxheap to minheap
{
if(num<maxheap.top())   //Push num to 1st half
{
int temp = maxheap.top();   //Save root of maxheap
maxheap.pop();  //Pop root of maxheap
maxheap.push(num);  //Push num to maxheap
minheap.push(temp); //Push previous saved root of maxheap to minheap
}
else    //Push num to 2nd half
minheap.push(num);
}
}
}

double findMedian() {
int lsize = maxheap.size();
int rsize = minheap.size();
if(lsize > rsize)  //Return top of maxheap for odd no of elements
return double(maxheap.top());
else    //Else return avg of top of maxheap and minheap
return (double(maxheap.top())+double(minheap.top()))/2;
}
};

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();