find_median_from_data_stream
1from heapq import heappush, heappop 2 3 4# @leet start 5class MedianFinder: 6 """ 7 This class finds the median of a stream of integers. 8 It does this by maintaining two heaps. 9 The low heap is a max-heap, to store the smaller half of the numbers. 10 The high heap is a min-heap, to store the higher half of the numbers. 11 12 When adding an item from the stream, the number is first added in inverse 13 to the max-heap. 14 Then, the largest item from the max-heap is moved to the min-heap. 15 Finally, if the min-heap is larger than the max-heap, the smallest number 16 from the min-heap is added to the max-heap. 17 18 When checking for the median, if the lengths of the two heaps are equal, 19 we take the sum of the top of both of the heaps and divide by two. 20 Otherwise, the max-heap is longer, and the top of the max-heap inverted 21 is the median, since it has a length % 2 == 1. 22 """ 23 24 def __init__(self): 25 self.low = [] 26 self.high = [] 27 28 def addNum(self, num: int) -> None: 29 heappush(self.low, -num) 30 heappush(self.high, -heappop(self.low)) 31 if len(self.low) < len(self.high): 32 heappush(self.low, -heappop(self.high)) 33 34 def findMedian(self) -> float: 35 if len(self.low) > len(self.high): 36 return -self.low[0] 37 else: 38 return (self.low[0] + self.high[0]) / 2 39 40 41# Your MedianFinder object will be instantiated and called as such: 42# obj = MedianFinder() 43# obj.addNum(num) 44# param_2 = obj.findMedian() 45# @leet end 46 47 48def test(): 49 assert 2 + 2 == 4
6class MedianFinder: 7 """ 8 This class finds the median of a stream of integers. 9 It does this by maintaining two heaps. 10 The low heap is a max-heap, to store the smaller half of the numbers. 11 The high heap is a min-heap, to store the higher half of the numbers. 12 13 When adding an item from the stream, the number is first added in inverse 14 to the max-heap. 15 Then, the largest item from the max-heap is moved to the min-heap. 16 Finally, if the min-heap is larger than the max-heap, the smallest number 17 from the min-heap is added to the max-heap. 18 19 When checking for the median, if the lengths of the two heaps are equal, 20 we take the sum of the top of both of the heaps and divide by two. 21 Otherwise, the max-heap is longer, and the top of the max-heap inverted 22 is the median, since it has a length % 2 == 1. 23 """ 24 25 def __init__(self): 26 self.low = [] 27 self.high = [] 28 29 def addNum(self, num: int) -> None: 30 heappush(self.low, -num) 31 heappush(self.high, -heappop(self.low)) 32 if len(self.low) < len(self.high): 33 heappush(self.low, -heappop(self.high)) 34 35 def findMedian(self) -> float: 36 if len(self.low) > len(self.high): 37 return -self.low[0] 38 else: 39 return (self.low[0] + self.high[0]) / 2
This class finds the median of a stream of integers. It does this by maintaining two heaps. The low heap is a max-heap, to store the smaller half of the numbers. The high heap is a min-heap, to store the higher half of the numbers.
When adding an item from the stream, the number is first added in inverse to the max-heap. Then, the largest item from the max-heap is moved to the min-heap. Finally, if the min-heap is larger than the max-heap, the smallest number from the min-heap is added to the max-heap.
When checking for the median, if the lengths of the two heaps are equal, we take the sum of the top of both of the heaps and divide by two. Otherwise, the max-heap is longer, and the top of the max-heap inverted is the median, since it has a length % 2 == 1.