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

class Solution {
public:
    //本题的含义为每次由Insert函数读进来一个数然后由GetMedian函数重新计算一次中位数
    //所以本题的关键思路即为选择什么排序算法最好
    //可能一上来就会有人选择快排，我觉得本题快排不好，因为对于本次求解来说，数组每次都是已经被上次求解排好序的了
    //而快排对于一个已经有序的数组来说时间复杂度可能会降到O（N²）所以本题可以选择归并或者堆排
    //这里我们使用小根堆,c++语言提供了大小根堆的现成结构可以直接使用
    priority_queue<int,vector<int>,greater<int>> heapArray;//建立小根堆
    void Insert(int num) {
        heapArray.push(num);
        return;
    }
    //这个函数的作用为求当前数组的中位数
    double GetMedian() { 
    double left,right;//这两个变量用来存储可能的中位数
        int size=heapArray.size();//记录当前堆中元素个数
      stack<int> S;//栈，用来存储从堆中弹出的元素
        int index=0;//用来记录当前栈中有多少个元素
        while(!heapArray.empty()){
            //从堆中弹出一个元素
            int data=heapArray.top();
            heapArray.pop();
            //将其放入栈中
            S.push(data);
            index++;
            if(size%2==0){//如果本次堆中的元素个数为偶数那么中位数是中间两个数
                if(index==size/2)
                    left=data;
                if(index==size/2+1){
                    right=data;
                    break;
                }
            }
            else{//个数是奇数
                if(index==(size-1)/2+1){
                    left=data;
                    break;
                }
            }
        }
        //结束后还要把栈中的元素放回堆中
        while(!S.empty()){
            int temp=S.top();
            S.pop();
            heapArray.push(temp);
        }
        if(size%2==0){
            return (left+right)/2;
        }
        else return left;
    }

};