二つのヒープパターン

- データストリームの中央値
class MedianFinder {
    // 小さい半分の要素を格納する最大ヒープ
    private PriorityQueue<Integer> maxHeap;
    // 大きい半分の要素を格納する最小ヒープ
    private PriorityQueue<Integer> minHeap;
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a); // 最大ヒープ
        minHeap = new PriorityQueue<>(); // 最小ヒープ
    }
    
    public void addNum(int num) {
        // 最大ヒープが空か、数値が最大ヒープのトップ以下なら最大ヒープに追加
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            // それ以外は最小ヒープに追加
            minHeap.offer(num);
        }
        
        // ヒープのバランスを調整
        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()) {
            // 要素数が偶数の場合、両方のヒープのトップの平均を返す
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            // 要素数が奇数の場合、最大ヒープのトップを返す
            return maxHeap.peek();
        }
    }
}