Approach
The main idea is to use two heaps to maintain the smaller half and the larger half of the numbers seen so far. We can use a max heap to store the smaller half of the numbers, and a min heap to store the larger half of the numbers.

The implementation involves the following steps:

Initialize two heaps: maxHeap (priority queue) and minHeap (priority queue with a custom comparator that makes it a min heap).
Insert a new number:

• If maxHeap is empty or the new number is smaller than or equal to the top element of maxHeap, add the number to maxHeap.

• Otherwise, add the number to minHeap.

• After adding the number to the appropriate heap, rebalance the heaps to ensure that the size difference between them is at most 1.

  1. If maxHeap is larger than minHeap by more than 1 element, move the top element of maxHeap to minHeap.
  2. If minHeap is larger than maxHeap, move the top element of minHeap to maxHeap.

Calculate the median:

• If the sizes of maxHeap and minHeap are equal, the median is the average of their top elements.
• If their sizes differ by 1, the median is the top element of the larger heap (maxHeap).

Time complexity:

• addNum: O(log n)
• findMedian: O(1)
• Overall: O(log n)

Space complexity:O(n)

class MedianFinder {
private:
	priority_queue<int> maxHeap; // stores the smaller half of numbers
	priority_queue<int, vector<int>, greater<int>> minHeap; // stores the larger half of numbers

public:
	MedianFinder() {
		}

void addNum(int num) {
    if (maxHeap.empty() || num <= maxHeap.top()) {
        maxHeap.push(num);
    } else {
        minHeap.push(num);
    }
    
    // Rebalance the heaps to ensure their sizes differ by at most 1
    if (maxHeap.size() > minHeap.size() + 1) {
        minHeap.push(maxHeap.top());
        maxHeap.pop();
    } else if (minHeap.size() > maxHeap.size()) {
        maxHeap.push(minHeap.top());
        minHeap.pop();
    }
}

double findMedian() {
    if (maxHeap.size() == minHeap.size()) {
        return (maxHeap.top() + minHeap.top()) / 2.0;
    } else {
        return maxHeap.top();
    }
}

};