# Median in data stream

## Title Description

How to get the median in a data stream? If an odd number is read from the data stream, the median is the number in the middle after all the numbers are sorted. If even numbers are read from the data stream, the median is the average of the middle two numbers after all the numbers are sorted. We use the Insert() method to read the data stream and the getmedia () method to get the median of the currently read data.

https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=11216&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## Code

```class Solution {
public:
vector<int> max;  // Maximum, large top reactor
vector<int> min;  // Minimum, small top reactor
void Insert(int num)
{
int len = max.size() + min.size();
if(len%2 == 0){  // There are even data at present, insert the current data into the small top heap
if(min.size() > 0 && num > min[0]){
int temp = min[0];
min.push_back(num);
pop_heap(min.begin(),min.end(),greater<int>());
max.push_back(temp);
push_heap(max.begin(),max.end(),less<int>());
min.pop_back();
}
else{
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());
}
}
else{
if(max.size() > 0 && num < max[0]){
int temp = max[0];
max.push_back(num);
pop_heap(max.begin(),max.end(),less<int>());
min.push_back(temp);
push_heap(min.begin(),min.end(),greater<int>());
max.pop_back();
}
else{
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
}
}
}

double GetMedian()
{
int len = max.size() + min.size();
if(len <= 0){
return 0;
}
if(len%2 == 0){
return ((max[0] + min[0]) / 2.0);
}
else{
return max[0];
}
}
};
```

Tags: less

Posted on Sun, 01 Dec 2019 18:01:09 -0800 by FramezArt