295. Find Median from Data Stream

I followed the top rated solution. The idea is brilliant. It keeps two heaps. One heap keeps the smaller half array and the other keep the larger half array, i.e. all the numbers in small heap is less than or equal to the ones in large heap. And we always keep small heap size is larger than or equal to the large heap size. Given that, the median will be the small heap top if small heap size is larger than the large heap size OR the average of small heap top and large heap top.

1:  class MedianFinder {  
2:  private:  
3:    priority_queue<int> small;  
4:    priority_queue<int, vector<int>, greater<int>> large;  
5:  public:  
6:    // Adds a number into the data structure.  
7:    void addNum(int num) {  
8:      if (small.empty()) { small.push(num); return; }  
9:      if (small.size() > large.size()) {  
10:        small.push(num);  
11:        large.push(small.top());  
12:        small.pop();  
13:      } else {  
14:        if (small.top() >= num) {  
15:          small.push(num);  
16:        } else {  
17:          large.push(num);  
18:          small.push(large.top());  
19:          large.pop();  
20:        }  
21:      }  
22:    }  
23:    // Returns the median of current data stream  
24:    double findMedian() {  
25:      if (small.size() == large.size()) return (small.top()+large.top())/2.0;  
26:      else return small.top();  
27:    }  
28:  };  
29:  // Your MedianFinder object will be instantiated and called as such:  
30:  // MedianFinder mf;  
31:  // mf.addNum(1);  
32:  // mf.findMedian();