295. Find Median from Data Stream - cocoder39/coco39_LC GitHub Wiki

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.left = []
        self.right = []

    def addNum(self, num: int) -> None:
        if len(self.right) == len(self.left):
            heapq.heappush(self.right, -heapq.heappushpop(self.left, -num))
        else:
            heapq.heappush(self.left, -heapq.heappushpop(self.right, num))
        

    def findMedian(self) -> float:
        if len(self.right) > len(self.left):
            return self.right[0]
        
        return (self.right[0] - self.left[0]) / 2

class MedianFinder {
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        pq1.push(num);
        pq2.push(-pq1.top());
        pq1.pop();
        
        if (pq2.size() - pq1.size() > 1) {
            int larger_min = -pq2.top();
            pq2.pop();
            pq1.push(larger_min);
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        int m = pq1.size(), n = pq2.size();
        if (m + n == 0) {
            return 0;
        } else if ((m + n) % 2) {
            return -pq2.top();
        } else {
            return (pq1.top() - pq2.top()) / 2.0;
        }
    }
private:
    //pq1 is smaller side, max heap
    //pq2 is larger side, min heap
    priority_queue<int> pq1, pq2;
};