✅ [Python/C++/Java/Rust] two heaps + BONUS (explained)
\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.\n*\nThis solution employs two Binary Heaps* to maintain quick access to the median elements. Time complexity is
**\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.**\n****\nThis solution employs two *Binary Heaps* to maintain quick access to the median elements. Time complexity is logarithmic **O(logN)** to *add* and constant **O(1)** to *find*. Space complexity is linear: **O(N)**.\n\n**Comment.** When we have the analogous problem with the *mean*, just updating the sum and the count of all elements would work, becuase that\'s what the mean is all about. However, to obtain the *median*, we should have access to the precise value of the middle element(s). The problem is that this element changes every time a new one is added from the data stream. This leads us to the conclusion that we need to store all elements. But what data structure to use? The key observation here is that we need to have (and maintain) quick access to at most two elements (or just one in the case of an odd size). Thus, either of two structures would work:\n1. Two Binary Heaps maintaining small and large halves of numbers. On the top of each heap we would have the value that is closest to the median.\n2. Sorted array. This would allow to retrieve the median by just "looking in the middle".\n\nHere, I provide a solution with heaps (in four languagaes). In the **BONUS** section, I also demonstrate the second aproach using Python\'s *SortedList*.\n\n**Python.**\n```\nclass MedianFinder:\n\n    def __init__(self):\n        self.sh, self.lh = [], []\n\n    def addNum(self, num: int) -> None:\n\n        heappush(self.lh, -heappushpop(self.sh,-num))     # [1] always push numbers to the large half first\n        if len(self.lh) > len(self.sh):                   # [2] if it\'s longer then transfer to the small one;\n            heappush(self.sh, -heappop(self.lh))          #     this way, the small one will never be shorter\n\n    def findMedian(self) -> float:\n\n        if len(self.sh) != len(self.lh):                  # [3] for odd size, the smallest half is the one that \n            return -self.sh[0]                            #     stores the median by our design in [1] and [2]\n        else                                              # [4] for even size, take average between two middle\n            return (-self.sh[0] + self.lh[0]) / 2         #     values, one taken from each of the heaps\n```\n\nThis solution in other languages.\n\n<iframe src="https://leetcode.com/playground/axhiVgon/shared" frameBorder="0" width="800" height="450"></iframe>\n\n**\u2705 YOU MADE IT TILL THE BONUS SECTION... YOUR GREAT EFFORT DESERVES UPVOTING THIS POST!**\n\nAs a **BONUS**, I provide a solution in **Python** using *SortedList* that maintains a sorted array for the quick access to its middle elements.\n\n```\nfrom sortedcontainers import SortedList\n\nclass MedianFinder:\n\n    def __init__(self):\n        self.data = SortedList()\n\n    def addNum(self, num: int) -> None:\n        self.data.add(num)\n\n    def findMedian(self) -> float:\n        n = len(self.data)\n        return (self.data[n//2] + self.data[(n-1)//2]) / 2\n```
[]