Two Heaps Pattern

import java.util.*;
public class MedianFinder {
    // Max heap for smaller half (largest element on top)
    PriorityQueue<Integer> maxHeap;
    // Min heap for larger half (smallest element on top)
    PriorityQueue<Integer> minHeap;
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);  // Max heap
        minHeap = new PriorityQueue<>();  // Min heap (default)
    }
    public void addNum(int num) {
        // Add to max heap first
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        // Balance the heaps (sizes should differ by at most 1)
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            // Even number of elements - average of two middle elements
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            // Odd number - max heap has one more element
            return maxHeap.peek();
        }
    }
    public static void main(String[] args) {
        MedianFinder mf = new MedianFinder();
        mf.addNum(1);
        System.out.println("Median: " + mf.findMedian());  // 1.0
        mf.addNum(2);
        System.out.println("Median: " + mf.findMedian());  // 1.5
        mf.addNum(3);
        System.out.println("Median: " + mf.findMedian());  // 2.0
        mf.addNum(4);
        System.out.println("Median: " + mf.findMedian());  // 2.5
    }
}

import java.util.*;
public class SlidingWindowMedian {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] result = new double[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            // Add new element
            addNum(nums[i]);
            // Remove element going out of window
            if (i >= k) {
                removeNum(nums[i - k]);
            }
            // Calculate median when window is full
            if (i >= k - 1) {
                result[i - k + 1] = findMedian();
            }
        }
        return result;
    }
    private void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        rebalance();
    }
    private void removeNum(int num) {
        if (num <= maxHeap.peek()) {
            maxHeap.remove(num);
        } else {
            minHeap.remove(num);
        }
        rebalance();
    }
    private void rebalance() {
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    private double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
        return maxHeap.peek();
    }
    public static void main(String[] args) {
        SlidingWindowMedian swm = new SlidingWindowMedian();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        double[] medians = swm.medianSlidingWindow(nums, k);
        System.out.println("Medians: " + Arrays.toString(medians));
        // Output: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]
    }
}

import java.util.*;
public class IPO {
    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        // Min heap for projects by capital requirement
        PriorityQueue<int[]> minCapitalHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        // Max heap for profits of affordable projects
        PriorityQueue<int[]> maxProfitHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        // Add all projects to min heap
        for (int i = 0; i < n; i++) {
            minCapitalHeap.offer(new int[]{capital[i], profits[i]});
        }
        // Select k projects
        for (int i = 0; i < k; i++) {
            // Move all affordable projects to max profit heap
            while (!minCapitalHeap.isEmpty() && minCapitalHeap.peek()[0] <= w) {
                maxProfitHeap.offer(minCapitalHeap.poll());
            }
            // If no affordable projects, we're done
            if (maxProfitHeap.isEmpty()) {
                break;
            }
            // Pick the most profitable project
            w += maxProfitHeap.poll()[1];
        }
        return w;
    }
    public static void main(String[] args) {
        int k = 2;  // Can select 2 projects
        int w = 0;  // Initial capital
        int[] profits = {1, 2, 3};
        int[] capital = {0, 1, 1};
        int maxCapital = findMaximizedCapital(k, w, profits, capital);
        System.out.println("Maximum capital: " + maxCapital);
        // Output: 4
        // Pick project 0 (profit=1, capital=0), then project 2 (profit=3, capital=1)
    }
}