java中priorityqueue扩容与siftup/siftdown协同维护最小堆性质：默认初始容量11；容量>>1，o(logn)）；删除后调siftdown（子下标2k+1/2k+2，k
Java 中 PriorityQueue 的扩容和堆调整（siftUp/siftDown）是它高效支持动态插入、删除的核心机制。两者协同工作：扩容保障空间可用，而 siftUp/siftDown 维护堆序——即“父节点 ≤ 子节点”的最小堆性质（默认）。它们不追求全数组有序，只确保堆顶始终是最小元素。
扩容机制：分段式增长，兼顾效率与内存
初始容量为 11，后续扩容不是固定倍率，而是根据当前容量大小采用不同策略：
- 当当前容量 时：新容量 = 旧容量 × 2 + 2（例如 11 → 24 → 50 → 102）
- 当当前容量 ≥ 64 时：新容量 = 旧容量 + (旧容量 >> 1)，即扩大 50%（例如 64 → 96 → 144）
- 扩容通过
Arrays.copyOf实现，属于数组拷贝，时间复杂度 O(n)，但因触发频率低，均摊代价仍为 O(1)
siftUp：插入新元素时的“上浮”路径调整
调用 offer() 时，新元素先追加到数组末尾（下标 k = size），再执行 siftUp(k, x)。其逻辑是沿父节点链向上比较并交换，直到满足堆序：
- 父节点下标恒为 (k − 1) >>> 1（无符号右移，等价于 (k−1)/2 向下取整）
- 若新元素比父节点小（最小堆），则父节点下移，当前位置上移到父位，继续比较
- 终止条件：新元素 ≥ 父节点，或已到达根节点（
k == 0） - 时间复杂度：O(log n)，最坏情况从叶子升至根
siftDown：删除堆顶或重排时的“下沉”修复
调用 poll() 或 removeAt(i) 后，需将末尾元素补到空缺位置，再调用 siftDown(k, x) 向下修复。它从当前节点出发，持续与较小子节点比较并交换：
- 左子节点下标为 2×k + 1，右子为 2×k + 2
- 关键判断边界：half = size >>> 1（即第一个叶子节点下标），只要
k 就说明该节点有至少一个子节点 - 每次选两子中较小者比较；若当前元素 > 该子节点，则子节点上移，当前位置下移
- 终止条件：当前元素 ≤ 两子节点，或已落至叶子层
- 时间复杂度：O(log n)，最坏情况从根沉至叶
heapify：批量建堆的线性优化技巧
构造含初始集合的 PriorityQueue（如 new PriorityQueue(list)）时，并非逐个 offer（O(n log n)），而是直接调用 heapify()：
- 从最后一个非叶子节点开始（下标 (size >>> 1) − 1），逆序向前对每个节点执行
siftDown - 利用完全二叉树结构特性：叶子节点天然满足堆序，只需调整上层
- 该策略将建堆时间复杂度优化至 O(n)，是堆排序高效性的基础
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
