leetcode-heap

295. Find Median from Data Stream.py

class MedianFinder:
    """
    Problem Clarification 
        If it is a steam (dynamically update/delete/add array)?
            -> Yes
    Thought Process
    
        Brute Force:
            step1: maintain a array by each time we called addnum, we sorted again. ->O(nlogn)
                   or 
                   maintain a array by each time we called addnum
                    find insertion position using bs, O(logn)
                    insert num into array O(n)
            step2: calcuate median by
                if list is odd we return A[n//2]
                if list is even we return (A[n//2]+A[n//2-1])/2
                 -> O(1)
        
        [1,2]
        [2,3,4]
        [2,3,4,5]
           1 2
        PQ:
         we need two PQ. one is min-heap and the other one is max-heap.
         min-heap放比中位數大的數字，max-heap放比中位數小的數字, 因爲中位數右半邊的數放在min-heap，我才可以知道min-heap的Root是最接近中位數的那個數. 反之中位數左半邊的數放在max-heap, 我就可以知道max-heap的root是最接近中位數的那個數。
         
         step1: maintain two PQ and need to balanced abs(size of left pq-size of righ_pq) <1
         
         
    """
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.A = []

    def addNum(self, num: int) -> None:
        """
        O(nlogn)
        """
        self.A.append(num)
        self.A = sorted(self.A)

    def findMedian(self) -> float:
        """
        O(1)
        """
        n = len(self.A)
        if n % 2 == 1:
            return self.A[n//2]
        else:
            print (n//2)
            return (self.A[n//2]+self.A[n//2-1])/2

class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.right_min_heap = []
        self.left_max_heap = []
    
    def balance(self):
        if len(self.left_max_heap) - len(self.right_min_heap) ==2:
            #把左邊最大的元數拿出來放到右邊
            data = heapq.heappop(self.left_max_heap)
            heapq.heappush(self.right_min_heap, -data)
            return
        if len(self.left_max_heap) < len(self.right_min_heap):
            #把右邊最小的元數拿出來放到左邊
            data = heapq.heappop(self.right_min_heap)
            heapq.heappush(self.left_max_heap, -data)
            return
        
    def addNum(self, num: int) -> None:
        """
        O(logn)
        During the process, we want to make sure len(self.left_max_heap) >= len(self.righ_min_heap)
        
        Also, we to balance right and left pq.
        
        """
        if len(self.left_max_heap)==0:
            heapq.heappush(self.left_max_heap, -num)
            return
        if num <= -self.left_max_heap[0]:
            heapq.heappush(self.left_max_heap, -num)
        else:
            heapq.heappush(self.right_min_heap, num)
        
        # balance left/right
        self.balance()
            
    def findMedian(self) -> float:
        """
        O(1)
        """
        median = None
        if len(self.left_max_heap) > len(self.right_min_heap):
            # odd
            median = -self.left_max_heap[0]
        else:
            # even
            median = (-self.left_max_heap[0]+ self.right_min_heap[0]) / 2
        return median
        
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()