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

由于题目中没有对空间复杂度和时间复杂度做要求，所以上来先考虑较为直接的解法。
建立一个数组用于保存数据流，每次插入数据都将数据存入数组中，在调用获取中位数的方法时，先调用sort对数组进行排序，再获得中位数。

class Solution {
public:
    void Insert(int num) {
        array.push_back(num);
    }

    double GetMedian() { 
        sort(array.begin(),array.end());
        if(array.size()%2){
            return double(array.at((array.size() - 1)/2));
        }
        else{
            return (array.at((array.size() - 1)/2)+array.at((array.size() - 1)/2 + 1))/2.0;
        }
    }
private:
    vector<int> array;
};

注意到题目中涉及到堆的算法，考虑使用堆排序来解决。
选择使用priority_queue的队列，即优先队列，这个数据结构会根据优先级为队列内的元素进行排序，而排序使用的正是堆排序。
所以虽然说使用优先队列能跟堆扯上点关系，但编码过程中的思维逻辑是不涉及堆的。
基本思想很简单，维护两个优先队列，可以默认它们始终保持有序，而不需要认为排序。其中一个队列按升序排列，另一队列按降序排列，使升序队列的最小值永远大于降序队列的最大值。
在插入数据时，轮流插入升序队列与降序队列，当插入一个队列时不直接插入，而是先将其插入另一队列，在将另一队列的队头插入该队列，这样保证两个队列的大小关系。
这样构建的两个队列，其对头元素必定位于输入数列的中位数位置。

这种做法使用了priority_queue自带的内部排序，其实现方法是堆排序，其实跟手动调用sort的结果相差不多。比较重要的思想是那两个队列的关系。

class Solution {
public:
    void Insert(int num) {
        if(control){
            up.push(num);
            int temp = up.top();
            up.pop();
            down.push(temp);
        }
        else{
            down.push(num);
            int temp = down.top();
            down.pop();
            up.push(temp);
        }
        control = !control;
    }

    double GetMedian(){
        if(control){
            return double(up.top());
        }
        else{
            return (up.top() + down.top())/2.0;
        }
    }
private:
    priority_queue<int> up;
    priority_queue<int, vector<int>, greater<int>> down;
    bool control = false;
};