class Solution {

public:

    /*

    * 1.定义一个规则：保证左边(大顶堆)和右边(小顶堆)个数相差不大于1，且大顶堆的数值都小于等于小顶堆的数 *

      2.大小堆顶可以用优先序列实现

        插入规则：

        当插入数值小于左边的堆顶时候，就插入左边，否则插入右边堆。(注意初始为空时，插入不能比较)

        调整使得满足个数差<=1：

        正常时是只有两种情况：p=q或者p=q+1,由于每插一个值就会考虑调整,那么边界情况就是p=q+2或者p+1=q

          p=q+2时，弹出左边大顶堆p的堆顶，并将其插入到q

          p+1=q时，弹出右边小顶堆q的堆顶，并将其插入到p

    * 3. 如果是奇数：中位数mid=左边的堆顶，因为先插入到左边，再插入到右边；为奇数时，中位数就是两个堆顶的平均值.

    */

    priority_queue <int, vector<int>,less<int> > p; //大顶堆p，注意最后两个>>不能连写，否则是右移运算

    priority_queue <int,vector<int>,greater<int> > q;//小顶堆q

    void Insert(int num)

    {

        if(p.empty()||num<p.top())

            p.push(num);//队列push,vector是push_back()

        else

            q.push(num);

        if(p.size()==q.size()+)

            q.push(p.top()),p.pop();//队列,pop()是删除第一个元素，但没有返回值

        if(p.size()+==q.size())

            p.push(q.top()),q.pop();

    }

    double GetMedian()

    {

        return p.size()==q.size() ? (p.top()+q.top())/2.0 : p.top();//除以2.0返回double

    }

};