295. 数据流的中位数

利用堆的堆顶可以随时保持最大（小）元素的特性。使用两个堆来存储数据。

由于需要取中位数。要保持两个堆堆顶为中间的元素。
所以：

  • 构建一个最小堆用来存放较大的数。
  • 构建一个最大堆用来存放较小的数。

（比较绕，需要用心思考一下）

要随时保持两个堆的高度平衡。

这时，两堆堆顶就是数据中的中位数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class MedianFinder {
    public:
        /** initialize your data structure here. */
        MedianFinder() {
            
        }

        void addNum(int num) {
            if(smallNums.empty()){
                //往存放小元素的最大堆添加数据。
                smallNums.push(num);
                return;
            }
            //如果两个堆的高度相同。优先push进当前堆顶元素更大的那一个。
            if(largeNums.size() == smallNums.size()){
                if(smallNums.top() > num){
                    smallNums.push(num);
                }else{
                    largeNums.push(num);
                }
            }
            //为了保持两个堆的平衡 。如果两堆高度不一致，分两种情况讨论
            //1.存放较大元素的最小堆的高度大于存放较小元素的最大堆的高度达。
            
            else if(largeNums.size() > smallNums.size()){
                // 该数比存放较大元素的最小堆的堆顶要大。
                // 首先将该堆堆顶元素push进存放较小元素的最大堆中。
                // 再将该数push进存放较大元素的最小堆
                if(num > largeNums.top()){
                    smallNums.push(largeNums.top());
                    largeNums.pop();
                    largeNums.push(num);
                }
                // 该数比存放较大元素的最小堆的堆顶要小。
                // 直接push进存放较小元素的最大堆。
                else{
                    smallNums.push(num);
                }
            }
            //2.存放较大元素的最小堆的高度小于存放较小元素的最大堆的高度达。
            else if(largeNums.size() < smallNums.size()){
                // 该数比存放较小元素的最大堆的堆顶要小。（该数一定要进该堆）
                // 首先将该堆堆顶元素push进存放较大元素的最小堆中。
                // 再将该数push进存放较小元素的最大堆中。
                if(num < smallNums.top()){
                    largeNums.push(smallNums.top());
                    smallNums.pop();
                    smallNums.push(num);
                }
                // 该数比存放较小元素的最大堆的堆顶要大。
                // 直接push进存放较大元素的最小堆。
                else{
                    largeNums.push(num);
                }
            }
        }

        double findMedian() {
            // 两堆平衡，取中位数。
            if(smallNums.size() == largeNums.size()){
                return (((double)smallNums.top() + largeNums.top())/2 );
            }
            // 不平衡，谁高取谁的堆顶。
            else if(smallNums.size() > largeNums.size()){
                return smallNums.top();
            }
            return largeNums.top();
        }
    
    private: 
        // 存放较大元素的最小堆
        std::priority_queue<int, std::vector<int>, std::greater<int> > largeNums;
        // 存放较小元素的最大堆
        std::priority_queue<int> smallNums;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */