# 295. Find Median from Data Stream

For example: 1 2 -3 4 => the ans: -3 1 2 4 => Median is 1.5

separate into two **heaps** (minheap), **large and small**

**概念是分成兩群, 小的群取最大的, 大的群取最小的,** 

**統一都用min heap,  所以**加到 small 時, **都會用負的加入,** 

**透過**-large.poll(), 把小的加到small

```java
large.add((long)num);
small.add(-large.poll());
```

`if (large.size() < small.size()) {`&#x20;

用來維持兩邊 heap 數量平衡,&#x20;

當small 太多時, 利&#x7528;**`large.add(-small.poll()); 加回去large`**&#x20;

**`=> -small.poll() 此時雖然是其poll min, 但其實會是把"最大"的加回 large (因為之前都是把負過的值加到small), 因為之前負過, 所以要在負回來`**

當奇數個數時, **large 會比較多個數**,&#x20;

偶數個數時, large 和small　的個數會一樣

```java
        if (large.size() < small.size()) {
            large.add(-small.poll());
        }
```

### 奇數case

For example: 1 2 -3&#x20;

the ans: -3 1 2

### when 1 enter, large.add(1)

```
small: 
large: 1
```

small.add(-large.poll()) => small.add(-1)

```
small: -1
large:
```

\=> small size > large size (奇數時, 維持 large 比較多個數&#x20;

\=> -small.poll() -(-1) add to large&#x20;

```
small: 
large: 1
```

### when 2 enter, large.add(2)

```
small: 
large: 1, 2
```

small.add(-large.poll()) => small.add(-1)

```
small: -1

large: 2
```

### when -3 enter, large.add(-3)

```
small: -1

large: 2, -3
```

small.add(-large.poll()) => small.add(3)

```
small: -1, 3

large: 2
```

\=> small size > large size

\=> -small.poll() -(-1) add to large

```
small: 3 

large: 2, 1 => large 取最小 (min heap peek()
```

奇數時, 就取large 的最小即可

### 偶數case

For example: 1 2 -3 4

the ans: -3 1 2 4

small: 3, -1 => small 取最小  (min heap peek()

large: 2, 4 => large 取最小 (min heap peek()

偶數時, small large 兩邊數量相等,&#x20;

中位數: large 取最小, small 取最小(其實代表實際上最大, 因為加入時都作過負號),&#x20;

相加除2 ⇒ 2 -(-1) /2 = 1.5 (因為small 放入時都是放負的, 所以要用 - 去加)

time: O(logn)

space: O(n)

```java
class MedianFinder {
    
    private PriorityQueue<Long> large;
    private PriorityQueue<Long> small;

    /** initialize your data structure here. */
    public MedianFinder() {
        large = new PriorityQueue<>();
        small = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        large.add((long)num);
        small.add(-large.poll());
        if (large.size() < small.size()) {
            large.add(-small.poll());
        }
    }
    
    public double findMedian() {
        // notice divide by 2.0, or the presision lost
        return (large.size() > small.size()) ? large.peek() : (large.peek() - small.peek())/2.0;
    }
}

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