题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
思路：用大根堆和小根堆，将数字分为两组，要保证小根堆中的数字都比大根堆中的大。
这样，如果共有偶数个数，小根堆中最小的，和大根堆最大的，的平均数即为中位数。
我们采用如果当前为偶数个数，就插入小根堆，奇数个数就插入大根堆的方法。这样如果总和为奇数个，则为小根堆中最小的。
注意：每次插入时要判断，1.向小根堆中插入要判断，要插入的数是不是比大根堆中的数大
2.向大根堆中插入要判断，要插入的数是不是比小根堆中的数小
代码如下：
vector<int> minvec; vector<int> maxvec; void Insert(int num) { if(( (minvec.size()+maxvec.size()) & 1) == 0)//偶数,插入小根堆 { if(maxvec.size() > 0 && num < maxvec[0])//比大根堆的小 { maxvec.push_back(num); push_heap(maxvec.begin(),maxvec.end(),less<int>());//默认为大根堆，最后一个参数可以不放 num = maxvec[0]; pop_heap(maxvec.begin(),maxvec.end(),less<int>()); maxvec.pop_back(); } minvec.push_back(num); push_heap(minvec.begin(),minvec.end(),greater<int>()); } else//奇数插入大根堆 { if(minvec.size() > 0 && num > minvec[0])//比大根堆的小 { minvec.push_back(num); push_heap(minvec.begin(),minvec.end(),greater<int>());//默认为大根堆，最后一个参数可以不放 num = minvec[0]; pop_heap(minvec.begin(),minvec.end(),greater<int>()); minvec.pop_back(); } maxvec.push_back(num); push_heap(maxvec.begin(),maxvec.end(),less<int>()); } } double GetMedian() { double n = 0; int size = minvec.size()+maxvec.size(); if(size == 0) return n; else if( (size & 1) == 0) n = (maxvec[0] + minvec[0]) / 2.0; else n = minvec[0]; return n; }
下面来说一下，有关STL中heap函数的相关用法：
1.make_heap()是生成一个堆，大顶堆或小顶堆
参数如下：
make_heap(first ,last)；
make_heap(first ,last, cmpObject);
cmpObject：为less<>() 生成大根堆（默认值） greater<>() 生成小根堆
2.push_heap()是向堆中插入一个元素，并且使堆的规则依然成立
1.用push_heap之前必须调用make_heap创建一个堆
2. 数组push_back插入元素，然后再调用push_heap，它会使最后一个元素插到合适位置
3.push_heap中的_Compare和make_heap中的_Compare参数必须是一致的
3.pop_heap()是在堆的基础上，弹出堆顶元素。
1.它会将堆顶元素（即为数组第一个位置）和数组最后一个位置对调，然后你可以调用数组pop_back，删除这个元素
2.pop_heap中的_Compare和make_heap中的_Compare参数必须是一致的，不然会失败