[Python] 2 heaps solution, explained
The idea is to keep two heaps: one for the top half of our data and another is for down half of our data. \nIf we have even size 2n, then we will keep two heaps
The idea is to keep two heaps: one for the top half of our data and another is for down half of our data. \nIf we have even size `2n`, then we will keep two heaps with size `n`\nIf we have odd size `2n+1`, then we will keep size of the small heap `n+1` ans the size of large heap `n`.\n\nWhen we have new element `num`, we always put it to small heap, and then normalize our heaps: remove biggest element from the small heap and put it to the large heap. After this operation we can be sure that we have the property that the largest element in small heap is smaller than smaller elements in large heap.\n\nHowever after this step if we had `n, n` elements, we will have `n, n+1` elements, so we need to put one element from large heap to small heap.\n\n#### Complexity\nTime complexity is just `O(1)` to get median and `O(log n)` to add number. Space complexity is `O(n)` after `n` operations.\n\n#### Code\n```python\nclass MedianFinder:\n    def __init__(self):\n        self.small, self.large = [], [] \n\n    def addNum(self, num):\n        heappush(self.small, -num)           \n        heappush(self.large, -heappop(self.small))\n        \n        if len(self.small) < len(self.large):\n            heappush(self.small, -heappop(self.large))\n            \n    def findMedian(self):\n        if len(self.large) != len(self.small):\n            return -self.small[0]                  \n        else:\n            return (self.large[0] - self.small[0]) / 2 \n```\n\n#### Remark\nThere is also solution with `O(log n)` time complexities for both operations, if we use `Sorted List`
['Heap (Priority Queue)']