class Solution {
public:
    void Insert(int num) {
        if( 0==BigHeap.size() )
        {
            BigHeap.push(num);
        }
        else 
        {
            if( num<BigHeap.top() )
            {
                BigHeap.push(num);
                if( BigHeap.size()-SmallHeap.size()>1 )
                {
                    SmallHeap.push( BigHeap.top() );
                    BigHeap.pop();
                }
            }
            else
            {
                SmallHeap.push(num);
                if( SmallHeap.size()-BigHeap.size()>1 )
                {
                    BigHeap.push( SmallHeap.top() );
                    SmallHeap.pop();
                }
            }
        }


    }

    double GetMedian() { 
        if( BigHeap.size()==SmallHeap.size() )
        {
            return ( (double)BigHeap.top()+SmallHeap.top() )/2.0;
        }
        else
        {
            return BigHeap.size()>SmallHeap.size()? BigHeap.top() : SmallHeap.top();
        }
    }
private:
    priority_queue<int> BigHeap;    //大顶堆存，左边小的
    priority_queue<int, vector<int> , greater<int> > SmallHeap;
};