힙

/* ── Max-Heap 배열 기반 구현 ────────────────────────────── */
public class MaxHeap {
    private int[] data;
    private int   size;

    public MaxHeap(int capacity) { data = new int[capacity]; }

    private int  parent(int i) { return (i - 1) / 2; }
    private int  left(int i)   { return 2 * i + 1; }
    private int  right(int i)  { return 2 * i + 2; }
    private void swap(int i, int j) {
        int t = data[i]; data[i] = data[j]; data[j] = t;
    }

    /* 삽입 + Heapify-Up */
    public void offer(int val) {
        data[size++] = val;
        int i = size - 1;
        // 부모보다 크면 올라간다
        while (i > 0 && data[parent(i)] < data[i]) {
            swap(i, parent(i));
            i = parent(i);
        }
    }

    /* 루트(최댓값) 조회 */
    public int peek()  { return data[0]; }           // O(1)

    /* Extract-Max + Heapify-Down */
    public int poll() {
        int max = data[0];
        data[0] = data[--size];   // 마지막 원소를 루트로
        heapifyDown(0);
        return max;
    }

    private void heapifyDown(int i) {
        while (left(i) < size) {
            int largest = left(i);
            if (right(i) < size && data[right(i)] > data[largest])
                largest = right(i);
            if (data[i] >= data[largest]) break; // 힙 조건 만족
            swap(i, largest);
            i = largest;
        }
    }
}

/* ── 힙 정렬: 제자리 정렬 O(n log n), 추가 메모리 O(1) ─── */
public static void heapSort(int[] arr) {
    int n = arr.length;

    // 1단계: Build Max-Heap (마지막 내부 노드부터 heapify-down)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapifyDown(arr, i, n);   // O(n)

    // 2단계: 루트(최댓값)를 끝으로 이동하며 정렬
    for (int end = n - 1; end > 0; end--) {
        // 루트(최댓값) ↔ 마지막 원소 교환
        int t = arr[0]; arr[0] = arr[end]; arr[end] = t;
        // 힙 크기를 줄이고 루트 재정렬
        heapifyDown(arr, 0, end);  // O(log n)
    }
    // 오름차순 정렬 완료 — O(n log n) 전체
}

private static void heapifyDown(int[] arr, int i, int n) {
    while (2 * i + 1 < n) {
        int largest = 2 * i + 1; // 왼쪽 자식
        if (2 * i + 2 < n && arr[2 * i + 2] > arr[largest])
            largest = 2 * i + 2; // 오른쪽이 더 크면
        if (arr[i] >= arr[largest]) break;
        int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
        i = largest;
    }
}

/* ── Java PriorityQueue (Min-Heap 기본) ─────────────────── */
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(15); minHeap.offer(4); minHeap.offer(42);
minHeap.peek();   // 4  — 최솟값 O(1)
minHeap.poll();   // 4  — 최솟값 제거 O(log n)

/* ── Max-Heap: reverseOrder 사용 ─────────────────────────── */
PriorityQueue<Integer> maxHeap =
    new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(15); maxHeap.offer(4); maxHeap.offer(42);
maxHeap.peek();   // 42 — 최댓값 O(1)

/* ── K번째 최솟값: Min-Heap 활용 패턴 ────────────────────── */
public int kthSmallest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int n : nums) pq.offer(n);
    while (--k > 0) pq.poll();
    return pq.peek();
}

/* ── 다익스트라에서의 활용 (최소 비용 노드 추출) ─────────── */
PriorityQueue<int[]> pq =
    new PriorityQueue<>((a, b) -> a[1] - b[1]); // 비용 기준 Min-Heap
pq.offer(new int[]{0, 0});  // {노드, 비용}
while (!pq.isEmpty()) {
    int[] cur = pq.poll();     // 현재 최소 비용 노드
    // 인접 노드 탐색 및 거리 갱신...
}