堆和优先队列

private void siftUp(int i) {
    while (i > 0 && heap[i] < heap[parent(i)]) {  // 最小堆
        swap(i, parent(i));
        i = parent(i);
    }
}

private void siftDown(int i) {
    int n = size;
    while (true) {
        int l = left(i), r = right(i), smallest = i;
        if (l < n && heap[l] < heap[smallest]) smallest = l;
        if (r < n && heap[r] < heap[smallest]) smallest = r;
        if (smallest == i) break;
        swap(i, smallest);
        i = smallest;
    }
}

public void heapify(int[] arr) {
    this.heap = arr;
    this.size = arr.length;
    for (int i = size / 2 - 1; i >= 0; i--) siftDown(i);
}

public class MinHeap {
    private int[] heap;
    private int size;

    public MinHeap(int capacity) { heap = new int[capacity]; }

    public void insert(int value) {
        if (size == heap.length) resize();
        heap[size] = value;
        siftUp(size++);
    }

    public int extractMin() {
        if (size == 0) throw new NoSuchElementException();
        int min = heap[0];
        heap[0] = heap[--size];
        siftDown(0);
        return min;
    }

    public int peek() {
        if (size == 0) throw new NoSuchElementException();
        return heap[0];
    }

    public int size() { return size; }

    private void siftUp(int i) {
        while (i > 0 && heap[i] < heap[(i - 1) / 2]) {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    private void siftDown(int i) {
        while (true) {
            int l = 2 * i + 1, r = 2 * i + 2, smallest = i;
            if (l < size && heap[l] < heap[smallest]) smallest = l;
            if (r < size && heap[r] < heap[smallest]) smallest = r;
            if (smallest == i) break;
            swap(i, smallest);
            i = smallest;
        }
    }

    private void swap(int i, int j) { int t = heap[i]; heap[i] = heap[j]; heap[j] = t; }
    private void resize() { heap = Arrays.copyOf(heap, heap.length * 2); }
}

// 默认是最小堆
PriorityQueue<Integer> minPQ = new PriorityQueue<>();
minPQ.offer(50); minPQ.offer(30); minPQ.offer(70);
minPQ.poll();   // 30

// 自定义最大堆
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a, b) -> b - a);

// 自定义比较器
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);   // 按第一个字段排序

public void heapSort(int[] arr) {
    int n = arr.length;
    // 1. 建堆
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, n, i);
    // 2. 反复取堆顶，放到末尾
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        siftDown(arr, i, 0);
    }
}

private void siftDown(int[] arr, int n, int i) {
    while (true) {
        int l = 2*i + 1, r = 2*i + 2, smallest = i;
        if (l < n && arr[l] < arr[smallest]) smallest = l;
        if (r < n && arr[r] < arr[smallest]) smallest = r;
        if (smallest == i) break;
        swap(arr, i, smallest);
        i = smallest;
    }
}

// 用最小堆维护 K 个最大元素
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : nums) {
    pq.offer(x);
    if (pq.size() > k) pq.poll();      // 把最小的扔掉
}
return pq.peek();

// 双堆：最大堆存较小一半，最小堆存较大一半
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);  // 较小一半
PriorityQueue<Integer> minHeap = new PriorityQueue<>();                // 较大一半

void addNum(int num) {
    maxHeap.offer(num);
    minHeap.offer(maxHeap.poll());
    if (maxHeap.size() < minHeap.size()) maxHeap.offer(minHeap.poll());
}

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