数据流中的中位数，C++

维护两个堆，一个大值堆一个小值堆。

大值堆中维护已经加入的所有的元素的小的那一半

小值堆中维护已经加入的所有的元素的大的那一半

加入一个值，奇数次加入就先加入小值堆，再从小值堆中选一个最小值进入大值堆

偶数次加入就先加入大值堆，再从大值堆中选一个最大值进入小值堆

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 class Solution {
 5 public:
 6     Solution()
 7     {
 8         count = 0;
 9     }
10     void Insert(int num)
11     {
12         if (count % 2 ==  0)
13         {
14             minQue.push(num);
15             int fromMinQueToMaxQue = minQue.top();
16             //cout<<"fromMinQueToMaxQue: "<<fromMinQueToMaxQue<<endl; 
17             minQue.pop();
18             maxQue.push(fromMinQueToMaxQue);
19         } else {
20             maxQue.push(num);
21             int fromMaxQueToMinQue = maxQue.top();
22             //cout<<"fromMaxQueToMinQue: "<<fromMaxQueToMinQue<<endl; 
23             maxQue.pop();
24             minQue.push(fromMaxQueToMinQue);
25         }
26         count++;
27     }
28 
29     double GetMedian()
30     { 
31         if (count % 2 == 1)
32         {
33             return (double)maxQue.top();
34         } else {
35             return  ((double)minQue.top() + (double)maxQue.top()) / 2;
36         }
37     }
38 private:
39     int count;
40     priority_queue<int, vector<int>, less<int> > minQue;
41     priority_queue<int, vector<int>, greater<int> > maxQue;
42 };
43 int main()
44 {
45     Solution s = Solution();
46     s.Insert(5);
47     s.Insert(2);
48     s.Insert(3);
49     s.Insert(4);
50     cout<<s.GetMedian()<<endl;
51     return 0;
52     return 0;
53 }