힙 변형 — 이중 힙, 피보나치 힙, 그리고 실무의 선택

public class DoubleEndedPQ<T extends Comparable<T>> {
    private PriorityQueue<T> minHeap = new PriorityQueue<>();
    private PriorityQueue<T> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    private Map<T, Integer> deleted = new HashMap<>(); // 지연 삭제용

    public void add(T value) {
        minHeap.offer(value);
        maxHeap.offer(value);
    }

    public T peekMin() {
        cleanup(minHeap);
        return minHeap.peek();
    }

    public T peekMax() {
        cleanup(maxHeap);
        return maxHeap.peek();
    }

    public T pollMin() {
        cleanup(minHeap);
        T min = minHeap.poll();
        // maxHeap에서 즉시 삭제하지 않고, 나중에 정리 (지연 삭제)
        deleted.merge(min, 1, Integer::sum);
        return min;
    }

    public T pollMax() {
        cleanup(maxHeap);
        T max = maxHeap.poll();
        deleted.merge(max, 1, Integer::sum);
        return max;
    }

    // 지연 삭제: 꺼내려는 값이 이미 삭제된 것이면 스킵
    private void cleanup(PriorityQueue<T> heap) {
        while (!heap.isEmpty() && deleted.getOrDefault(heap.peek(), 0) > 0) {
            T top = heap.poll();
            deleted.merge(top, -1, Integer::sum);
            if (deleted.get(top) == 0) deleted.remove(top);
        }
    }
}

public class TreeMapDEPQ<T> {
    private TreeMap<T, Integer> map = new TreeMap<>();

    public void add(T value) {
        map.merge(value, 1, Integer::sum);
    }

    public T peekMin() { return map.firstKey(); }
    public T peekMax() { return map.lastKey(); }

    public T pollMin() {
        T min = map.firstKey();
        removeOne(min);
        return min;
    }

    public T pollMax() {
        T max = map.lastKey();
        removeOne(max);
        return max;
    }

    private void removeOne(T key) {
        int count = map.get(key);
        if (count == 1) map.remove(key);
        else map.put(key, count - 1);
    }
}

public class MedianFinder {
    // 작은 쪽 절반: 최대 힙
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    // 큰 쪽 절반: 최소 힙
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll()); // 균형 유지

        // maxHeap의 크기가 같거나 1개 더 많게 유지
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

피보나치 힙:
  min → [3] ↔ [7] ↔ [18]
         |         |
        [8]      [24]
         |
        [21]

1. Insert: 새 트리를 루트 리스트에 추가 (O(1))
   [3] ↔ [7] ↔ [1]  ← 1 추가

2. Delete-Min: 최소 노드 제거 → 자식들을 루트 리스트에 추가
   → Consolidation: 같은 차수의 트리를 합침

3. Decrease-Key: 값 감소 → 부모보다 작아지면 잘라서 루트로 올림 (O(1))
   → 부모가 자식 2개 이상 잃으면 부모도 잘라냄 (Cascading Cut)

이진 힙 삽입:   배열에 값 하나 추가 + sift up
피보나치 힙 삽입: 노드 객체 생성 + 포인터 여러 개 조정

실제 시간: 이진 힙이 5~10배 빠를 수 있음

이진 힙:     [1, 3, 5, 7, 9, 11]  ← 연속 메모리, 캐시 적중률 높음
피보나치 힙:  각 노드가 개별 객체    ← 메모리 분산, 캐시 미스 빈번

4-ary 힙:
        1
    / | | \
   3  5  7  9

// Pairing Heap 노드
class PairingNode<T> {
    T value;
    PairingNode<T> child;   // 첫 번째 자식
    PairingNode<T> sibling; // 형제
}

// 스레드 안전한 우선순위 큐
PriorityBlockingQueue<Task> queue = new PriorityBlockingQueue<>();

// 프로듀서 스레드
queue.put(new Task(1, "긴급 작업"));

// 컨슈머 스레드
Task task = queue.take(); // 없으면 블로킹