295

I did this

public class MedianFinder {
    private readonly PriorityQueue<int, int> minHeap;
    private readonly PriorityQueue<int, int> maxHeap;
 
    public MedianFinder() {
        minHeap = new PriorityQueue<int, int>();
        maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a,b) => b.CompareTo(a)));
    }   
    
    public void AddNum(int num) {
        if (maxHeap.Count == 0) {
            maxHeap.Enqueue(num, num);
            return;
        }
            
        //Case 1 - maxHeap greater
        if (maxHeap.Count > minHeap.Count) {
            if (maxHeap.Peek() > num) {
                int maxTop = maxHeap.Dequeue();
                maxHeap.Enqueue(num, num);
                minHeap.Enqueue(maxTop, maxTop);
            }
            else minHeap.Enqueue(num, num);
        }
 
        //Case 2 - minHeap greater
        else if (minHeap.Count > maxHeap.Count) {
            if (minHeap.Peek() < num) {
                int minTop = minHeap.Dequeue();
                minHeap.Enqueue(num, num);
                maxHeap.Enqueue(minTop, minTop);
            }
            else maxHeap.Enqueue(num, num);
        }
 
        //Case 3 - both equal
        else {
                if (minHeap.Peek() <= num)
                     minHeap.Enqueue(num, num);
                else
                    maxHeap.Enqueue(num, num);
        }
    }
    
    public double FindMedian() {
        if (minHeap.Count > maxHeap.Count)
            return minHeap.Peek();
        else if (maxHeap.Count > minHeap.Count)
            return maxHeap.Peek();
        else 
            return ((long)minHeap.Peek() + maxHeap.Peek()) / 2.0;
    }
}
 
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.AddNum(num);
 * double param_2 = obj.FindMedian();
 */

---

This cleaner one works,

public class MedianFinder {
    private readonly PriorityQueue<int, int> low =
        new(Comparer<int>.Create((a, b) => b.CompareTo(a)));   // max-heap: lower half
    private readonly PriorityQueue<int, int> high = new();      // min-heap: upper half
 
    public void AddNum(int num) {
        low.Enqueue(num, num);              // 1. put it in the lower half
        int top = low.Dequeue();            // 2. move the lower half's largest up, so every value in low <= every value in high
        high.Enqueue(top, top);
 
        if (high.Count > low.Count) {       // 3. rebalance: low is always equal in size or one bigger
            int t = high.Dequeue();
            low.Enqueue(t, t);
        }
    }
 
    public double FindMedian() =>
        low.Count > high.Count
            ? low.Peek()                                // odd count: the middle is low's top
            : (low.Peek() + (double)high.Peek()) / 2;   // even count: average of both tops
}
 
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.AddNum(num);
 * double param_2 = obj.FindMedian();
 */

The idea: low holds the smaller half (max-heap), high holds the larger half (min-heap). The median is always at the tops. Two rules must hold after every add:

1. Everything in low ≤ everything in high.
2. low has the same size as high, or one more.

public void AddNum(int num) {
    low.Enqueue(num, num);       // step 1
    int top = low.Dequeue();     // step 2
    high.Enqueue(top, top);
 
    if (high.Count > low.Count) {   // step 3
        int t = high.Dequeue();
        low.Enqueue(t, t);
    }
}

Steps 1 and 2: guarantee rule 1. Push num into low, then pop low’s largest and send it to high. Whatever stays in low is smaller than or equal to what was just sent up, so the halves are correctly separated. You never compare num against anything, because the max-heap does the comparing.

Step 3: guarantee rule 2. Steps 1 and 2 net out to high gaining one element and low staying the same size. If high is now bigger than low, move high’s smallest back to low.