Two heap approach with Python O(log n) insert, O(1) median
\n"""\naddNum\nRuntime: O(log n)\nSpacetime: O(n)\n\nfindMedian\nRuntime: O(1)\nSpacetime: O(1)\n"""\nfrom heapq import *\n\nclass MedianFinder:\n\n    def __in
```\n"""\naddNum\nRuntime: O(log n)\nSpacetime: O(n)\n\nfindMedian\nRuntime: O(1)\nSpacetime: O(1)\n"""\nfrom heapq import *\n\nclass MedianFinder:\n\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        self.min_heap: List[int] = []\n        self.max_heap: List[int] = []\n        \n\n    def addNum(self, num: int) -> None:\n        heappush(self.max_heap, -heappushpop(self.min_heap, num))\n        \n        if len(self.max_heap) > len(self.min_heap):\n            heappush(self.min_heap, -heappop(self.max_heap))\n        \n\n    def findMedian(self) -> float:\n        has_even_count = len(self.max_heap) == len(self.min_heap)\n\n        if has_even_count:\n            return (-self.max_heap[0] + self.min_heap[0]) / 2.0\n        return float(self.min_heap[0])\n```
['Heap (Priority Queue)', 'Python', 'Python3']