数据流中的中位数
    题目链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
    图片.png

    思路：维护一个最大堆和一个最小堆，最大堆总是存储比中位数小的一半数据，最小堆总是存储比中位数大的一半数据，从而实现O(1)返回中位数。需要注意维护一个invariant：两个堆的size要么相等要么差1，因此在插入新数据时：

    • 若此时两个堆size相等，先插入到最小堆，然后将最小堆的栈顶数据pop出来插入到最大堆
    • 若此时两个堆size差1（必然是最大堆比最小堆多1个），则先插入到最大堆，然后将最大堆的栈顶数据pop出来插入到最小堆

    上述过程能够保证两个堆总是存放正确的数据。

    参考代码：

    1. class MedianFinder {
    2. public:
    3.     /** initialize your data structure here. */
    4.     MedianFinder() {
    6.     }
    8.     void addNum(int num) {
    9.         if (maxHeap.size() == minHeap.size()) {
    10.             minHeap.push(num);
    11.             maxHeap.push(minHeap.top());
    12.             minHeap.pop();
    13.             return;
    14.         }
    15.         maxHeap.push(num);
    16.         minHeap.push(maxHeap.top());
    17.         maxHeap.pop();
    18.     }
    20.     double findMedian() {
    21.         if (maxHeap.size() == minHeap.size()) {
    22.             return (maxHeap.top() + minHeap.top())/2.0;
    23.         }
    24.         return maxHeap.top();
    25.     }
    26. private:
    27.     priority_queue<int, vector<int>, less<int>> maxHeap;
    28.     priority_queue<int, vector<int>, greater<int>> minHeap;
    29. };