[python3] Max and Min heaps || SortedList || O(log n)
The main issue we need to solve in this problem is to have a list that is always sorted in some way so we can access the middle one/two values easily. A binary 
The main issue we need to solve in this problem is to have a list that is always sorted in some way so we can access the middle one/two values easily. A binary search tree is ideal for this since we can add value to it in O(log n). In python, we use SortedList.\n\n```\nfrom sortedcontainers import SortedList\nclass MedianFinder:\n\n    def __init__(self):\n        self.s = SortedList()\n\n    def addNum(self, num: int) -> None:\n        self.s.add(num)\n\n    def findMedian(self) -> float:\n        l = len(self.s)\n        if l%2==0:\n            return (self.s[l//2-1]+self.s[l//2])/2\n        return self.s[l//2]\n\n```\n\nI don\'t think the interviewer is looking for an API call during the interview, so I don\'t think giving the above answer can pass it. And a follow-up question would be, please implement the binary search tree...\nAnother idea is to use a ```maxHeap``` to store the numbers in the first half of the list and a ```minHeap``` to store the numbers in the second half of the list. In order to get the median efficiently, we need to balance the two heaps so that the median/s is/are always on the top of the heap/s. To do this, each time when we add a number, we check the length of the two heaps and make sure``` maxHeap``` either has the same length as the ```minHeap``` (the entire list has an even length), or the ``` maxHeap``` has one more value than the ```minHeap``` (the entire list has an odd length).\n```\nclass MedianFinder:\n\n    def __init__(self):\n        ### max heap to store the first half of the list\n        self.maxHeap = []\n        ### min heap to store the second half of the list\n        self.minHeap = []\n\n    def addNum(self, num: int) -> None:\n        ### push num into the correct heap\n        if not self.maxHeap or num <= -self.maxHeap[0]:\n            heappush(self.maxHeap, -num)\n        else:\n            heappush(self.minHeap, num)\n        \n        ### banance the two heaps so that each of them representing half of the list\n        ### for odd length list, len(maxHeap) == len(minHeap)+1\n        ### for even length list, len(maxHeap) == len(minHeap)\n        if len(self.minHeap) > len(self.maxHeap):\n            heappush(self.maxHeap, -heappop(self.minHeap)) \n        elif len(self.maxHeap) > len(self.minHeap)+1:\n            heappush(self.minHeap, -heappop(self.maxHeap)) \n\n    def findMedian(self) -> float:\n        \n        ### if the length of entire list is even, \n        ### get the mean of the two middle values\n        if (len(self.maxHeap)+len(self.minHeap))%2==0:\n            return (-self.maxHeap[0]+self.minHeap[0])/2\n        \n        ### when odd, we know that the median is in maxHeap\n        return -self.maxHeap[0]\n```\n\n**Upvote** if you like this post.\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.
[]