Median In Stream

来源：CC150

原帖：http://www.fgdsb.com/2015/01/03/median-in-stream/#more
            http://www.hawstein.com/posts/20.9.html

题目：
Create the data structure for a component that will receive a series of numbers over the time and, when asked, returns the median of all received elements.

代码：

 class Online {  
 public:  
     void add_number(int n) {  
         if (max_heap.empty() || max_heap.top() > n) {  
             max_heap.push(n);  
             if (max_heap.size() - min_heap.size() > 1) {  
                 int m = max_heap.top();   
                 max_heap.pop();  
                 min_heap.push(m);  
             }  
         } else {  
             min_heap.push(n);  
             if (min_heap.size() > max_heap.size()) {  
                 int m = min_heap.top();  
                 min_heap.pop();  
                 max_heap.push(m);  
             }  
         }  
     }  
   
     int get_median() const {  
         int total = max_heap.size() + min_heap.size();  
         if (total % 2 == 0) {  
             return (max_heap.top() + min_heap.top()) / 2;  
         } else {  
             return max_heap.top();  
         }  
     }  
   
 private:  
     priority_queue<int,vector<int>,less<int>> max_heap;  
     priority_queue<int,vector<int>,great<int>> min_heap;      
 };