#PriorityQueue 原理

// PriorityQueue 底层是二叉堆（小顶堆）
// 完全二叉树存储在数组中
// 父节点索引 = (i - 1) / 2
// 左子节点索引 = 2 * i + 1
// 右子节点索引 = 2 * i + 2

// 小顶堆：每个节点的值 <= 其子节点的值
// 堆顶元素 = 最小值

// 数组示例：[1, 3, 5, 4, 6, 7, 8]
// 对应的完全二叉树：
//         1
//        / \
//       3   5
//      / \ / \
//     4  6 7  8

public boolean offer(E e) {
    if (e == null) throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1); // 扩容
    size = i + 1;
    if (i == 0)
        queue[0] = e; // 第一个元素
    else
        siftUp(i, e); // 上浮
    return true;
}

// siftUp：让新元素上浮到正确位置
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x); // 自定义比较器
    else
        siftUpComparable(k, x); // 自然顺序
}

// 自然顺序的 siftUp
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0) // 如果大于等于父节点，停止
            break;
        queue[k] = e; // 父节点下沉
        k = parent;
    }
    queue[k] = key; // 放入正确位置
}

public E poll() {
    if (size == 0) return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0]; // 堆顶
    E x = (E) queue[s]; // 最后一个元素
    queue[s] = null;
    if (s != 0)
        siftDown(0, x); // 下沉
    return result;
}

// siftDown：让最后一个元素下沉到正确位置
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

// 自然顺序的 siftDown
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    int half = size >>> 1; // 非叶子节点索引上界

    while (k < half) {
        int child = (k << 1) + 1; // 左子节点
        Object c = queue[child];
        int right = child + 1;

        // 找较小的子节点
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];

        if (key.compareTo((E) c) <= 0)
            break;

        queue[k] = c; // 较小子节点上浮
        k = child;
    }
    queue[k] = key;
}

// 小顶堆（默认）：越小优先级越高
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(1);
minHeap.add(3);
minHeap.poll(); // 1

// 大顶堆：自定义比较器
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(5);
maxHeap.add(1);
maxHeap.add(3);
maxHeap.poll(); // 5

// 自定义对象
PriorityQueue<Person> pq = new PriorityQueue<>(
    Comparator.comparingInt(Person::getAge)
);
pq.add(new Person("Alice", 30));
pq.add(new Person("Bob", 25));
pq.poll(); // Bob（年龄最小）

// PriorityQueue：非阻塞
PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer("a");

// PriorityBlockingQueue：阻塞
PriorityBlockingQueue<String> pbq = new PriorityBlockingQueue<>();
pbq.offer("a");
pbq.take(); // 队列空时阻塞

// offer：O(log n) — 上浮，最多到根
// poll：O(log n) — 下沉，最多到叶子
// peek：O(1) — 堆顶就是最小值
// contains：O(n) — 需要遍历