// 基于本地 JDK 源码 (D:/1ForCode/JAVA_Source, java.base, 2024 版), java.util.PriorityQueue
public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

    // ...

    transient Object[] queue;       // 完全二叉树按层序摊平进数组, queue[0] 是堆顶

    int size;

    private final Comparator<? super E> comparator;  // null 则退回元素自身的 Comparable

    transient int modCount;         // fail-fast 计数, 迭代中 offer/poll 会让迭代器抛 CME

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();   // null 进堆第一次 compareTo 就会炸, 干脆入口拦掉
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        siftUp(i, e);                           // 放到最后一个空位, 然后一路上浮
        size = i + 1;
        return true;
    }

    public E peek() {
        return (E) queue[0];                    // 空堆返回 null
    }

    public E poll() {
        final Object[] es;
        final E result;
        if ((result = (E) ((es = queue)[0])) != null) {
            modCount++;
            final int n;
            final E x = (E) es[(n = --size)];   // 拿最后一个元素
            es[n] = null;
            if (n > 0) {
                final Comparator<? super E> cmp;
                if ((cmp = comparator) == null)
                    siftDownComparable(0, x, es, n);    // 末元素填到顶, 一路下沉
                else
                    siftDownUsingComparator(0, x, es, n, cmp);
            }
        }
        return result;
    }

    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // 小堆翻倍(+2), 大堆加 50%
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity,
                oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1);
        queue = Arrays.copyOf(queue, newCapacity);
    }
}

// 基于本地 JDK 源码 (D:/1ForCode/JAVA_Source, java.base, 2024 版), java.util.PriorityQueue
    private static <T> void siftUpComparable(int k, T x, Object[] es) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;         // 父下标: (k-1)/2
            Object e = es[parent];
            if (key.compareTo((T) e) >= 0)      // 不小于父亲, 堆序已满足, 停
                break;
            es[k] = e;                          // 父亲被拉下来占坑, 不是 swap
            k = parent;
        }
        es[k] = key;                            // x 最终落座, 全程只写它一次
    }

    private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
        Comparable<? super T> key = (Comparable<? super T>)x;
        int half = n >>> 1;                     // 第一个叶子的下标; 叶子无需下沉
        while (k < half) {
            int child = (k << 1) + 1;           // 先假设左孩子更小
            Object c = es[child];
            int right = child + 1;
            if (right < n &&
                ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
                c = es[child = right];          // 右孩子更小就换成右
            if (key.compareTo((T) c) <= 0)      // 不大于较小的孩子, 停
                break;
            es[k] = c;                          // 小孩子上来占坑
            k = child;
        }
        es[k] = key;
    }

    // 从乱序数组原地建堆: 从最后一个非叶节点倒着逐个下沉, Floyd 算法, O(n)
    private void heapify() {
        final Object[] es = queue;
        int n = size, i = (n >>> 1) - 1;
        final Comparator<? super E> cmp;
        if ((cmp = comparator) == null)
            for (; i >= 0; i--)
                siftDownComparable(i, (E) es[i], es, n);
        else
            for (; i >= 0; i--)
                siftDownUsingComparator(i, (E) es[i], es, n, cmp);
    }