這類題是一類典型的two priority queue的題目。維護兩個heap，一個MinHeap，一個MaxHeap。本解法中，MaxHeap的在奇數時會多一個，奇數時返回MaxHeap的top（注意這里面的邏輯，如果先往MaxHeap放，那么MaxHeap就一定要多一個）。另外注意，c++此題直接用multiset來實現priority_queue。如果priority_queue里面裝的是int，直接用multiset了

Leetcode 295：

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        size = 0;
    }
    
    void addNum(int num) {
        size++;
        if(m1.empty() || num < *m1.begin()){
            m1.insert(num);
        }
        else{
            m2.insert(num);
        }
        if(m1.size() > m2.size() + 1){
            m2.insert(*m1.begin());
            m1.erase(m1.begin());
        }
        
        if(m2.size() > m1.size()){
            m1.insert(*m2.begin());
            m2.erase(m2.begin());
        }
    }
    
    double findMedian() {
        if(size % 2 == 0){
            return (*m1.begin() + *m2.begin()) / 2.0;
        }
        else{
            return *m1.begin();
        }
    }
private:
    multiset<int, greater<int>> m1; // max heap
    multiset<int> m2; // min heap
    int size;
};

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

Lintcode 81：
Lintcode的題目要求稍有不同。偶數個時，不是除平均，而是返回小的那個數。

 class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: the median of numbers
     */
    void insertNumber(int num){
        if(max_heap.empty() || num < *max_heap.begin()){
            max_heap.insert(num);
        }
        else{
            min_heap.insert(num);
        }
        
        if(max_heap.size() > min_heap.size() + 1){
            min_heap.insert(*max_heap.begin());
            max_heap.erase(max_heap.begin());
        }
        
        if(min_heap.size() > max_heap.size()){
            max_heap.insert(*min_heap.begin());
            min_heap.erase(min_heap.begin());
        }
        
    }
    
    vector<int> medianII(vector<int> &nums) {
        // write your code here
        vector<int> ret;
        if(nums.empty()) return ret;
        
        for(auto it : nums){
            insertNumber(it);
            ret.push_back(*max_heap.begin());
        }
        return ret;
    }
private:
    multiset<int, greater<int>> max_heap;
    multiset<int> min_heap;
};

Lintcode 360： Sliding Window Median

這道題也是用維護兩個heap來求解。難點在于要維護一個size = k的window，而不考慮其它元素。

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of the element inside the window at each moving
     */
    void insert(int num){
        if(m1.empty() || num <= *m1.begin()){
            m1.insert(num);
        }else{
            m2.insert(num);
        }
        balanceSet();
    } 
    
    void balanceSet(){
        if(m1.size() > m2.size() + 1){
            int cur = *m1.begin();
            m1.erase(m1.begin());
            m2.insert(cur);
        }
        if(m2.size() > m1.size()){
            int cur = *m2.begin();
            m2.erase(m2.begin());
            m1.insert(cur);
        }
    }
     
    void erase(int num){
        if(num <= *m1.begin()){
            m1.erase(m1.find(num));
        }else{
            m2.erase(m2.find(num));
        }
        balanceSet();
    } 
    vector<int> medianSlidingWindow(vector<int> &nums, int k) {
        // write your code here
        vector<int> ret;
        if(nums.empty() || k <= 0) return ret;
        int idx = min(k, (int)nums.size());
        for(int i=0; i<idx; i++){
            insert(nums[i]);
        }
        ret.push_back(*m1.begin());
        for(int i=idx; i<nums.size(); i++){
            erase(nums[i - k]);
            insert(nums[i]);
            ret.push_back(*m1.begin());
        }
        return ret;
    }
private:
    multiset<int, greater<int>> m1;
    multiset<int> m2;
};