LeetCode 295.Find Median from Data Streamデータストリームの中位数(C++/Java)

タイトル:
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example, [2,3,4] , the median is  3 [2,3] , the median is  (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.

double findMedian() - Return the median of all elements so far.

 
Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

分析:
中位数は、シーケンステーブルの中央にある数です.リスト長が偶数の場合、中央値は中間の2つの数の平均です.
中位数関数を呼び出すたびに再計算しないほうがいいのは明らかです.これにより、時間の複雑さが高くなります.
 剣指offerには同じ問題があり、この問題を参考にしてこの問題を理解することができ、剣指offer-63.データストリームの中位数(C++/Java)を指す.
プログラム:
C++

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        index = 0;
    }
    
    void addNum(int num) {
        if(index % 2 == 0){
            minHeap.push(num);
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
        else{
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
        index++;
    }
    
    double findMedian() {
        double res = 0;
        if(index % 2 == 0){
            res = (double)(maxHeap.top() + minHeap.top()) / 2;
            return res;
        }
        else{
            res = (double)maxHeap.top();
            return res;
        }
    }
private:
    priority_queue <int, vector<int>, less<int> > maxHeap;
    priority_queue <int, vector<int>, greater<int> > minHeap;
    int index;
};

Java

class MedianFinder {

    /** initialize your data structure here. */
    public MedianFinder() {
        minHeap = new PriorityQueue();
        maxHeap = new PriorityQueue(11,new Comparator(){
            @Override
            public int compare(Integer i1,Integer i2){
                return i2-i1;
            }
        });
        index = 0;
    }
    
    public void addNum(int num) {
        if(index % 2 == 0){
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
        else{
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }
        index++;
    }
    
    public double findMedian() {
        double res = 0;
        if(index % 2 == 0){
            res = (minHeap.peek() + maxHeap.peek()) / 2.0;
            return res;
        }
        else{
            res =  maxHeap.peek();
            return res;
        }
    }
    private PriorityQueue minHeap;
    private PriorityQueue maxHeap;
    private int index;
}