> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/06_heap/295.-find-median-from-data-stream.md).

# 295. Find Median from Data Stream

<https://leetcode.com/problems/find-median-from-data-stream/>

## solution

* 双heap
  * 一个最小堆，一个最大堆。数据分成两部分，中位数就是前半部分的最大值，后半部分的最小值
  * 新加入元素，先判断该加入小堆还是大堆，再调整维持平衡
  * 总个数为奇数时，放在哪个堆里可以提前定义好

```python
import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # 极大堆(python都是极小堆，因此是负数进入). 数据中小的一半进入max_heap
        self.min_heap = []  # 数据中大的一半进入min_heap

    def addNum(self, num: int) -> None:
        if not self.max_heap or num <= -self.max_heap[0]:  # -max_heap[0] 是小数据中的最大值
            # 多一个的奇数的话，进入max_heap. findMedian奇数的话就从max_heap中取
            heapq.heappush(self.max_heap, -num)
            if len(self.max_heap) - len(self.min_heap) > 1:
                heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        else:
            heapq.heappush(self.min_heap, num)
            if len(self.max_heap) < len(self.min_heap):
                heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def findMedian(self) -> float:
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2.0
        return -self.max_heap[0]
```

时间复杂度：O(nlog(n))\
空间复杂度：O(n)

* SortedDict

```python
```

时间复杂度：O()\
空间复杂度：O()

* 二分法
  * 使用二分法插入，使得数据流是有序的

```python
```

## follow up

[480. Sliding Window Median](/mle-interview/01_leetcode/15_tree_map/480.-sliding-window-median.md)