Find Median from Data Stream

题目地址：
https://leetcode.com/problems/find-median-from-data-stream/description/

题目：

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.

Examples: 

[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.

For example:

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

解题思路：
这道题就是用两个优先队列来做。每次加之前，先要加进去另外一个堆里面。

代码：

PriorityQueue<Integer> maxHeap; // heap with smaller valuePriorityQueue<Integer> minHeap; // heap with larger valueboolean sizeEqual = true;

public MedianFinder() {
    maxHeap = new PriorityQueue<>((x, y) -> y - x);
    minHeap = new PriorityQueue<>();
}

public void addNum(int num) {
    if(sizeEqual){
        minHeap.add(num);
        maxHeap.add(minHeap.poll());
    }
    else{
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
    }
    sizeEqual = !sizeEqual;
}

public double findMedian() {
    if(sizeEqual){
        return ((double)minHeap.peek() + (double)maxHeap.peek()) / 2;
    }
    else{
        return (double)maxHeap.peek();
    }
}