如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
最开始的思路就是用map或者set存储。习惯写python就想直接用median的key去访问median，但是C++ STL的map或者set没有key这个东西，如果用迭代器那么访问元素复杂度是O（n）
看到很多解法是用两个堆来做，一个最大堆，一个最小堆，一开始不理解。后来发现这样的好处是把数据总体切分为两部分，一部分（最大堆）所有元素都比另一部分（最小堆）小。然后当有新元素需要insert的时候，根据现有元素总数奇偶，决定先压入哪个堆，然后弹出一个元素，弹出元素放入另一个堆。
最后的答案处理，根据元素总数奇偶，决定从两个堆分别取还是从特定的那个取。
class Solution{
public:
void Insert(int num){
if (maxS.size() == minS.size()){
maxS.insert(num);
minS.insert(*maxS.begin());
maxS.erase(maxS.begin());
}
else{
minS.insert(num);
maxS.insert(*minS.begin());
minS.erase(minS.begin());
}
}
double GetMedian(){
int num = maxS.size() + minS.size();
double median;
if ((num&1)==1){
median = *minS.begin();
}
else{
median = (*maxS.begin() + *minS.begin()) / 2.0;
}
return median;
}
private:
multiset<int, greater<int> > maxS;
multiset<int, less<int> > minS;
};