Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.
  For example:

add(1)
add(2)
findMedian() -> 1.5
add(3)
findMedian() -> 2

解题思路

使用两个priority_queue来模拟两个堆，其中的一个大根堆minH用来存储较大的那一半元素，另一个小根堆maxH用来存储较小的那一半元素。则，中位数要么是其中一个堆（元素较多的堆）的top元素，要么是两个堆的top元素的均值。

实现代码

C++:

// Runtime: 212 ms
class MedianFinder {
public:
    // Adds a number into the data structure.
    void addNum(int num) {
       minH.push(num);
       int n = minH.top();
       minH.pop();
       maxH.push(n);
       int len1 = maxH.size();
       int len2 = minH.size();
       if (len1 > len2)
       {
           n = maxH.top();
           maxH.pop();
           minH.push(n);
       }
    }

    // Returns the median of current data stream
    double findMedian() {
        int len1 = maxH.size();
        int len2 = minH.size();
        if (len1 == len2)
        {
            return (maxH.top() + minH.top()) / 2.0;
        }
        else
        {
            return len1 > len2 ? maxH.top() : minH.top();
        }
    }

private:
    priority_queue<int, vector<int>, less<int>> maxH;
    priority_queue<int, vector<int>, greater<int>> minH;
};

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

Java:

// Runtime: 50 ms
class MedianFinder {
    private Queue<Integer> maxH = new PriorityQueue<Integer>(Collections.reverseOrder());
    private Queue<Integer> minH = new PriorityQueue<Integer>();
    // Adds a number into the data structure.
    public void addNum(int num) {
        minH.offer(num);
        int n = minH.poll();
        maxH.offer(n);
        int len1 = maxH.size();
        int len2 = minH.size();
        if (len1 > len2) {
            n = maxH.poll();
            minH.offer(n);
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        int len1 = maxH.size();
        int len2 = minH.size();
        if (len1 == len2) {
            return (maxH.peek() + minH.peek()) / 2.0;
        }
        else {
            return len1 > len2 ? maxH.peek() : minH.peek();
        }
    }
};

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