题意

动态维护中位数

分析

维护两个大小平衡的大根堆和小根堆，两个堆顶的元素就是可能的中位数。

class Solution {
public:
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    void insert(int num){
        max_heap.push(num);
        if(!min_heap.empty() && min_heap.top() < max_heap.top()){
            int min_top = min_heap.top(), max_top = max_heap.top();
            min_heap.pop(), max_heap.pop();
            max_heap.push(min_top), min_heap.push(max_top);
        }
        int max_size = max_heap.size(), min_size = min_heap.size();
        if(max_size > min_size + 1){
            int t = max_heap.top();
            max_heap.pop();
            min_heap.push(t);
        }
    }

    double getMedian(){
        if(max_heap.size() != min_heap.size())return max_heap.top();
        else return (max_heap.top() + min_heap.top()) / 2.0;
    }
};