295. Find Median from Data Stream

heap O(logn)

class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) { // 3次调整
        left.push(num); // 先放到左边最大堆调整
        right.push(left.top()); left.pop(); // 再取左边最大堆最大的数放到右边最小堆调整
        if (left.size() < right.size()) { // 如果左边数少则取右边最小堆最小的数放到左边最大堆再调整，要始终保持左边最大堆的数不少于右边最小堆的数
            left.push(right.top()); right.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        return left.size() > right.size() ? left.top() : (left.top() + right.top()) * 0.5;
    }

private:
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int> > right;
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        if (left.empty() && right.empty()) {
            median = num;
            left.push(num);
            return;
        }
        if (num < median) {
            if (left.size() > right.size()) {
                right.push(left.top());
                left.pop();
            }
            left.push(num);
        }
        else {
            if (right.size() > left.size()) {
                left.push(right.top());
                right.pop();
            }
            right.push(num);
        }
        if (left.size() > right.size())
            median = left.top();
        else if (right.size() > left.size())
            median = right.top();
        else
            median = (left.top() + right.top()) / 2.0;
    }

    // Returns the median of current data stream
    double findMedian() {
        return median;
    }

private:
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int> > right;
    double median;
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();