# [LeetCode 295. Find Median from Data Stream](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3810/)
### Daily challenge Jul 11, 2021 (HARD)

>The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.
>
>For example, for **`arr = [2,3,4]`**, the median is **`3`**.
For example, for **`arr = [2,3]`**, the median is **`(2 + 3) / 2 = 2.5.`**
Implement the MedianFinder class:
>
>**`MedianFinder()`** initializes the MedianFinder object.
**`void addNum(int num)`** adds the integer num from the data stream to the data structure.
**`double findMedian()`** returns the median of all elements so far. Answers within
10^-5^ of the actual answer will be accepted.

:::info
Example 1:
**Input**
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
**Output**
[null, null, null, 1.5, null, 2.0]

**Explanation**
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
:::

:::warning
**Constraints:**
* -10^5^ <= num <= 10^5^
* There will be at least one element in the data structure before calling findMedian.
* At most 5 * 10^4^ calls will be made to addNum and findMedian.
:::

---

### Approach 1 : Two Heap :book:
**`92 ms`** **`O(logn)`**

使用 **max_heap** (resp. **min_heap**) 代表**較小** (resp. **較大**) 部分的陣列。

進行 **`addNum(num)`** 時，num 先與 top element of two Heaps 比較，如果**小於等於** max_heap ，表示 num 屬於較小的部分。相反 num 則屬於較大的部分。

接下來進行 **rebalance**，確保兩個 Heap 長度相差不超過 1。

最後 **median** 就會是 two top of elements (當長度相等時)，或是其中一個 Heap 的 top of element (取決於哪個的長度較長)。

> 假設 : max_heap = 1 2 3 / min_heap = 4 5
> **addNum(0)** ---> max_heap = 0 1 2 3 / min_heap = 4 5
> **rebalance** ---> max_heap = 0 1 2 / min_heap = 3 4 5
> **median** = *`(max_heap.top() + min_heap.top() ) / 2`* or *`max_heap.top()`*
> or *`min_heap.top()`*, depend on the size of two heaps.

class MedianFinder {
public:
    /* initialize your data structure here. */
    MedianFinder() {
    }
    
    priority_queue<int, vector<int>, less<int>> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    
    void addNum(int num) {
        // insert num
        if(max_heap.empty() || num <= max_heap.top())   max_heap.push(num);
        else    min_heap.push(num);
        
        // rebalance
        if(min_heap.size() > max_heap.size() + 1){
            max_heap.push(min_heap.top());
            min_heap.pop();
        }
        else if(min_heap.size() + 1 < max_heap.size()){
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }
    
    double findMedian() {
        if(max_heap.size() == min_heap.size())  return (max_heap.top() + min_heap.top()) / 2.0;
        else if(max_heap.size() > min_heap.size())  return max_heap.top();
        else    return min_heap.top();            
    }
};

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