Python 3 Min-heap and Max-heap approach explained
If an ordered integer list contains odd elements, then a median is the N//2nd element - i.e [1,2,3,4,5]\'s median is 3. If an ordered integer list contains even
If an ordered integer list contains odd elements, then a median is the N//2nd element - i.e [1,2,3,4,5]\'s median is 3. If an ordered integer list contains even elements, then a median is (N//2nd element + (N//2 + 1)th element) / 2 - i.e. [1,2,3,4,5,6]\'s median is (3 + 4) / 2 == 3.5. In other words:\n* the median of an odd-sized list is a largest number of the first half of its elements.\n* the median of an even-sized list is a (largest number of the first half of its elements + smallest number of the second half of its elements) / 2\n\nThe idea is to initialize two data structures: 1) one that stores the first half of its elements (`first_half`) and 2) one that stores the second half of its elements (`second_half`). For the `addNum()` method, we\'ll need to push a new number into either `first_half` or `second_half`. You may think that we must maintain the elements\' ordering such that both data structures are sorted in ascending order. However, that\'s not true because we\'re only interested in retrieving:\n* `first_half`\'s largest number\n*  `second_half`\'s smallest number\n\nIt seems like max-heap and min-heap is a good candidate for this use-case because the former allows us to retrieve (peek) the largest number in constant time & the latter allows us to retrieve (peek) the smallest number in constant time. \n\nNext, we must maintain the heaps such that:\n* they both have the same exact size when we add an even number of elements in total\n* `first_half` contains one extra element compared to `second_half` when we add an odd number of elements in total.\n\nThe way to achieve this is by:\n1) heappush the number into `first_half`\n2) heappop `first_half`\'s element & heappush it into `second_half`\n3) If `first_half`\'s size < `second_half`\'s size, then we\'ll heappop the  `second_half`\'s element & heappush it into `first_half`.\n\nTo paint a picture, let\'s do a quick dry-run:\n```\nadd 3\n=====\nstep one:\n---------\nfirst_half: [-3] (we must multiply by -1 for Python\'s max-heap)\nsecond_half: []\n\nstep two\n--------\nfirst_half: []\nsecond_half: [3] (first_half current stores negative number. hence, we must multiply it by -1 again)\n\nstep three\n----------\nfirst_half: [-3] (first_half\'s length is less than second_half. hence, we must push the number back to it)\nsecond_half: []\n\nadd 5\n=====\nstep one:\n---------\nfirst_half: [-5, -3] (we must multiply by -1 for Python\'s max-heap)\nsecond_half: []\n\nstep two\n--------\nfirst_half: [-3]\nsecond_half: [5] (first_half current stores negative number. hence, we must multiply it by -1 again)\n\nstep three\n----------\nfirst_half: [-3]\nsecond_half: [5] (we keep as is b/c first_half\'s size == second_half\'s size)\n```\n\nFor the `findMedian()` method, we\'ll check if `first_half`\'s size == `second_half`\'s size. If that\'s the case, then it implies that we\'ve added an even number of elements in total. Hence, we\'ll return (`first_half`\'s first element  + `second_half`\'s first element) / 2. Otherwise, we\'ll return `first_half`\'s first element instead. *FYI: We want to return the first element because max-heap/min-heap\'s first element is the largest/smallest number.*\n\n```\nclass MedianFinder:\n\n    def __init__(self):\n        self.first_half = []\n        self.second_half = []\n\n    def addNum(self, num: int) -> None:\n        # We must multiply the number by -1 because\n        # Python doesn\'t include built-in max-heap atm.\n        heappush(self.first_half, -num)\n        popped_element = heappop(self.first_half)\n        heappush(self.second_half, -popped_element)\n        \n        if len(self.first_half) < len(self.second_half):\n            popped_element = heappop(self.second_half)\n            heappush(self.first_half, -popped_element)\n        \n    def findMedian(self) -> float:\n        if len(self.first_half) == len(self.second_half):\n            return (-self.first_half[0] + self.second_half[0]) / 2\n        return -self.first_half[0]\n```\n\n\\\n**time/space complexity for addNum()**\nThe time complexity for the `addNum()` method is O(log(N/2)) ~= O(logN)  because heappush and heappop operation requires logarithmic additional runtime to finish. Although `first_half` and `second_half` contains about N/2 elements, it can be rounded up to N.\n\nThe space complexity for the `addNum()` method is O(1) because heappush and heappop operation require constant additional spaces to complete.\n\n\\\n**time/space complexity for findMedian()**\nThe time complexity for the `findMedian()` method is O(1) because we\'re executing a fixed number of operations.\n\nThe space complexity for the `findMedian()` method is O(1) because we\'re only only retrieving an element from `first_half` and `second_half`.\n\n\\\n**time/space complexity throughout the entire problem**\nThe entire problem entails O(NlogN) additional runtime because every add operation requires logN additional runtime to complete.\n\nThe entire problem entails O(N) additional memory because we must store N/2 elements into `first_half` and `second_half` (N/2 + N/2 == N).
['Heap (Priority Queue)', 'Python', 'Python3']