题解 | #数据流中的中位数#

#include <queue>
#include <vector>
class Solution {
public:
    priority_queue<int>min_q;//存放较小数据的大根堆，堆顶即为最大数
    priority_queue<int,vector<int>,greater<int>>max_q; //存放较大数据的小根堆，堆顶即为最小数
    void Insert(int num) {
        //约定当为奇数时，从大根堆取中位数，固先将数放入大根堆
        min_q.push(num);
        max_q.push(min_q.top());//将大根堆最大数放入小根堆，保持小根堆的数始终大于大根堆
        min_q.pop();
        //当小根堆的数比大根堆多时，从小根堆取最小数放入大根堆，保持大根堆大小始终大于小根堆
        if(max_q.size()>min_q.size()){
            min_q.push(max_q.top());
            max_q.pop();
        }
    }
    double GetMedian() { 
        if(min_q.size()>max_q.size()){
            return (double)min_q.top();
        }
        return (double)(min_q.top()+max_q.top())/2;
    }

};