###### tags: `Leetcode` `hard` `heap` `design` `python` `Top 100 Liked Questions`

# 295. Find Median from Data Stream

## [題目連結:] https://leetcode.com/problems/find-median-from-data-stream/

## 題目:
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.

**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

## 解題想法:
* 題目為實作兩函式:
* addNum(): 加入數字到數組
* findMedian(): 求中位數
* 若當前數組個數為偶數:
* 中位數為: 數組中間兩數的平均
* 若當前數組個數為奇數:
* 中位數為: 數組中間的那個數字

* 使用兩個heap:
* 對於理想情況對於由小到大排好的數組nums: [左小...中位數...右大] ex:[1,2,3,4]
* 使用兩heap紀錄比中位數大or小的數:
* minHeap
* maxHeap
* 目標為: 時刻注意讓len(minHeap)，len(maxHeap)長度差控制在1以內
* 則最終:
* 若len(minHeap)==len(maxHeap):
* 表示數組長度為偶數:
* 取minHeap[0]、maxHeap[0]平均
* 若len(minHeap)!=len(maxHeap):
* 表示數組長度為奇數:
* 取長度多1的heap，其heap[0]即為中位數
* minHeap: ex: 需存[1,2]
* 存左小(小於中位數的所有值)
* 希望該heap內為由大到小排序(這樣才能直接取minHeap[0]進行運算)
* 但對於python heapq內定為heap[0]最小
* 因此對於加入minHeap的數，一律先加上'負號'用以標示:
* 則當前最大的數，加上負號後成為最小，順利待在minHeap[0]
* 對於ex，希望存為[-2,-1]
* maxHeap: ex: 需存[3,4]
* 存右大(大於中位數的所有值)
* 希望該heap內為由正常小到大排序
* 對於ex，希望存為[3,4]

* 示意圖:
* 

## Python:

from heapq import heappush,heappop
class MedianFinder(object):

    def __init__(self):
        self.maxHeap=[] #存大於中位數的
        self.minHeap=[] #存小於中位數的 (需加上負號再存入)

    def addNum(self, num):
        """
        :type num: int
        :rtype: None
        """
        if not self.maxHeap or num>self.maxHeap[0]:
            heappush(self.maxHeap,num)
            #判斷長度:
            if (len(self.maxHeap)-len(self.minHeap))>1:
                heappush(self.minHeap,-heappop(self.maxHeap))
        else:
            heappush(self.minHeap,-num)
            if (len(self.minHeap)-len(self.maxHeap))>1:
                heappush(self.maxHeap,-heappop(self.minHeap))
                
    def findMedian(self):
        """
        :rtype: float
        """
        #偶數
        if len(self.maxHeap)==len(self.minHeap):
            return float((self.maxHeap[0]-self.minHeap[0]))/2
        else:
            if len(self.maxHeap)>len(self.minHeap):
                return self.maxHeap[0]
            else:
                return -self.minHeap[0]

if __name__ == '__main__':
    res=MedianFinder()
    res.addNum(2)
    res.addNum(1)
    res.addNum(3)
    res.addNum(4)
    mid=res.findMedian()
    print(mid) #2.5