[C++/Java/Python] MinHeap, MaxHeap Solution - Picture explain - Clean & Concise
\u2714\uFE0F Solution 1: MaxHeap to store a half of low numbers, MinHeap to store a half of high numbers\n- The idea is to divide numbers into 2 balanced halves
**\u2714\uFE0F Solution 1: MaxHeap to store a half of low numbers, MinHeap to store a half of high numbers**\n- The idea is to divide numbers into 2 balanced halves, one half `low` stores low numbers, the other half `high` stores high numbers. To access the median in `O(1)`, we need a data structure that give us the maximum of `low` half and the minimum of `high` half in `O(1)`. That\'s where `maxHeap` and `minHeap` come into play.\n- We use `maxHeap` to store a half of **low numbers**, top of the maxHeap is the highest number among low numbers.\n- We use `minHeap` to store a half of **high numbers**, top of the minHeap is the lowest number among high numbers.\n- We need to balance the size between `maxHeap` and `minHeap` while processing. Hence after adding `k` elements, \n\t- If `k = 2 * i` then `maxHeap.size = minHeap.size = i`\n\t- If `k = 2 * i + 1`, let `maxHeap` store 1 element more than `minHeap`, then `maxHeap.size = minHeap.size + 1`.\n- When adding a new number `num` into our  `MedianFinder`:\n\t- Firstly, add `num` to the `maxHeap`, now `maxHeap` may contain the big element (which should belong to `minHeap`). So we need to balance, by removing the highest element from `maxHeap`, and offer it to `minHeap`. \n\t- Now, the `minHeap` might hold more elements than `maxHeap`, in that case, we need to balance the size, by removing the lowest element from `minHeap` and offer it back to `maxHeap`.\n- When doing `findMedian()`:\n\t- If `maxHeap.size > minHeap.size` return top of the `maxHeap`, which is the highest number amongs low numbers.\n\t- Else if `maxHeap.size == minHeap` return the `(maxHeap.top() + minHeap.top()) / 2`.\n\n![image](https://assets.leetcode.com/users/images/0eb8feba-cbfa-4f73-8d26-9aad226bdbc5_1626016093.9717174.png)\n\n\n<iframe src="https://leetcode.com/playground/FbECj5Ww/shared" frameBorder="0" width="100%" height="420"></iframe>\n\n**Complexity**\n- Time:\n\t- Constructor: `O(1)`\n\t- addNum: `O(logN)`\n\t- findMedian: `O(1)`\n- Space: `O(N)`\n\n---\n\n**\u2714\uFE0F Solution 2: SortedList**\n```python\nfrom sortedcontainers import SortedList\nclass MedianFinder:\n\n    def __init__(self):\n        self.arr = SortedList()\n\n    def addNum(self, num: int) -> None:\n        self.arr.add(num)\n\n    def findMedian(self) -> float:\n        n = len(self.arr)\n        if n % 2 == 1:\n            return self.arr[n//2]\n        return (self.arr[n//2] + self.arr[n//2-1]) / 2\n```\n**Complexity**\n- Time:\n\t- Constructor: `O(1)`\n\t- addNum, findMedian: `O(logN)`\n- Space: `O(N)`\n\n
[]