Two Heaps Pattern

class MedianFinder {
    private PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    private PriorityQueue<Integer> upper = new PriorityQueue<>(); // min-heap

    public void addNum(int num) {
        lower.offer(num);               // always add to lower first
        upper.offer(lower.poll());      // balance: move max of lower to upper
        if (upper.size() > lower.size()) // keep lower >= upper in size
            lower.offer(upper.poll());
    }

    public double findMedian() {
        if (lower.size() > upper.size())
            return lower.peek(); // odd total: median is max of lower
        return (lower.peek() + upper.peek()) / 2.0; // even: average of two middles
    }
}

// Example:
// addNum(1): lower=[1], upper=[]
// addNum(2): lower=[1], upper=[2]
// findMedian() = (1+2)/2 = 1.5
// addNum(3): lower=[2,1], upper=[3]
// findMedian() = 2

public double[] medianSlidingWindow(int[] nums, int k) {
    TreeMap<Integer, Integer> lower = new TreeMap<>(); // simulates max-heap
    TreeMap<Integer, Integer> upper = new TreeMap<>();
    // ... (implementation using TreeMap for O(log k) remove)
    double[] result = new double[nums.length - k + 1];
    // Full implementation uses a balance counter and TreeMap for O(log k) deletes
    return result;
}

// Pick k projects to maximize capital
// Two heaps: max-heap by profit for affordable projects, min-heap by capital for all projects
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    int n = profits.length;
    PriorityQueue<int[]> locked = new PriorityQueue<>((a,b) -> a[0]-b[0]); // min-heap by capital
    PriorityQueue<int[]> available = new PriorityQueue<>((a,b) -> b[1]-a[1]); // max-heap by profit

    for (int i = 0; i < n; i++) locked.offer(new int[]{capital[i], profits[i]});

    for (int i = 0; i < k; i++) {
        // Unlock all projects we can afford
        while (!locked.isEmpty() && locked.peek()[0] <= w)
            available.offer(locked.poll());
        if (available.isEmpty()) break;
        w += available.poll()[1]; // pick most profitable
    }
    return w;
}

         lower (max-heap)  |  upper (min-heap)
  ... 1, 2, 3, [4]        |  [5], 6, 7, 8 ...
                  ↑ median(s) ↑