data stream median

最大堆 median 最小堆

1）持续插入； 2）插入过程中调整3个部分； 3）调整完成后输出当前median

code

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of numbers
     */
    vector<int> medianII(vector<int> &nums) {
        // write your code here
        vector<int> ret;
        if(nums.size() == 0)
        {
            return ret;
        }

        priority_queue<int> left; // max heap
        priority_queue<int, vector<int>, greater<int>> right; // min heap

        int cur = nums[0];
        ret.push_back(nums[0]);

        for(int i = 1; i<nums.size(); i++)
        {
            //cout<<i<<endl;
            int now = nums[i];
            if(now < cur)
            {
                left.push(now);
            }
            else
            {
                right.push(now);
            }

            //cout<<i<<endl;

            int lsize = (int)left.size();
            int rsize = (int)right.size();

            if(lsize - rsize >= 1)
            {
            //cout<<"w"<<" "<<left.size()<<" "<<right.size()<<endl;
                right.push(cur);
                cur = left.top();
                left.pop();
            }
            else if(rsize - lsize > 1)
            {
            //cout<<"x"<<endl;
                left.push(cur);
                cur = right.top();
                right.pop();
            }
            ret.push_back(cur);
        }

        return ret;

    }
};