Python two heap solution with full explanation
\nimport heapq\n\nclass MedianFinder:\n    \n    \'\'\'\n    We have a max heap representing the sorted left half of the stream, and a min heap representing the
```\nimport heapq\n\nclass MedianFinder:\n    \n    \'\'\'\n    We have a max heap representing the sorted left half of the stream, and a min heap representing the sorted right half of the stream.\n    The tops of these heaps represent the middle of the stream so far.\n    \n    To get the median:\n        - if len(left) == len(right): return (left[0] + right[0]) / 2\n        - elif len(left) > len(right): return left[0]\n        - else: return right[0]\n        \n    To add a number x:\n        If x <= left[0], add to left. Else, add to right.\n        If abs(len(left) - len(right)) > 1: rebalance heaps.\n        \n    To rebalance:\n        Pop an element from the bigger heap and add it to the smaller heap.\n        \n    Adding a number: O(log n) time, as there could be at most 2 pushes and 1 pop (log n).\n    Finding the median: O(1), since we just look at the 0th elements of the heaps.\n    Space: O(n), since we store every element in the heaps.\n    \'\'\'\n\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        \n        self.left = []\n        self.right = []\n        \n\n    def addNum(self, num: int) -> None:\n        if not self.left or num <= -self.left[0]:\n            heapq.heappush(self.left, -num) # we use negative numbers to make it a max heap, default python heap is a min heap\n        else:\n            heapq.heappush(self.right, num)\n            \n        # rebalance here\n        if abs(len(self.left) - len(self.right)) > 1:\n            if len(self.left) > len(self.right):\n                elt = -heapq.heappop(self.left) # negate to get it back to original number\n                heapq.heappush(self.right, elt)\n            else:\n                elt = heapq.heappop(self.right)\n                heapq.heappush(self.left, -elt) # negate due to max heap\n\n\n    def findMedian(self) -> float:\n        \n        # remember to negate the left values!\n        \n        if len(self.left) == len(self.right):\n            return (-self.left[0] + self.right[0]) / 2\n        elif len(self.left) > len(self.right):\n            return -self.left[0]\n        else:\n            return self.right[0]\n        \n\n\n# Your MedianFinder object will be instantiated and called as such:\n# obj = MedianFinder()\n# obj.addNum(num)\n# param_2 = obj.findMedian()\n```
['Heap (Priority Queue)', 'Python', 'Python3']