priorityqueue插入时必经上浮（siftup）操作：新元素追加至数组末尾，沿父节点链（索引为(i−1)/2）逐层比较交换，直至满足小顶堆序性，时间复杂度o(log n)，不触发下沉。

直接看 JDK 源码里 PriorityQueue 的核心逻辑，关键就在两个私有方法：siftUp 和 siftDown。它们不对外暴露，但整个堆的动态平衡全靠这两个操作驱动。

上浮操作（siftUp）发生在插入时

每次调用 offer() 或 add()，新元素先追加到数组末尾（索引 size），然后立即触发 siftUp：

• 从当前索引 k 开始，计算父节点索引：(k - 1) >> 1（等价于 (k - 1) / 2，整除）
• 若使用自然序（comparator == null），比较 queue[k] 和 queue[parent]
• 在小顶堆中，如果 queue[k] ，就交换；否则停止
• 更新 k = parent，继续向上，直到到达根（k == 0）或满足堆序

下沉操作（siftDown）发生在出队时

poll() 先取走 queue[0]，再把末尾元素（queue[size-1]）挪到索引 0，接着调用 siftDown：

Java Development Manual

Java开发手册规约集合，基于阿里巴巴Java开发手册（嵩山版）。 涵盖7大维度：编程规约、异常日志、单元测试、安全规约、MySQL数据库、工程结构、设计规约。 当用户需要：(1) 编写或审查Java代码 (2) 检查命名/代码规范 (3) 处理异常和日志 (4) 编写单元测试 (5) 安全编码 (6) 数据库设...

下载

• 从根开始（k = 0），先找两个孩子中较小的那个：左孩子 2k+1，右孩子 2k+2
• 只跟更小的孩子比（小顶堆要求父 ≤ 子），若 queue[k] > queue[child]，就交换
• 更新 k = child，重复直到没有孩子，或当前节点已不大于两个孩子
• 注意：它不回溯、不跟父比，路径唯一向下

源码定位技巧

在 OpenJDK 21+ 的 PriorityQueue.java 中：

• siftUp 实现有两个重载版本：siftUpComparable（自然序）和 siftUpUsingComparator（自定义比较器）
• siftDown 同样分 siftDownComparable 和 siftDownUsingComparator
• 所有入口方法如 offer、poll、removeAt 都会间接调用它们
• 数组字段是 transient Object[] queue，初始容量为 11，扩容按 old + (old >> 1)（即 ×1.5）进行

为什么不用递归而用循环

上浮和下沉都用 while 循环实现，而非递归：

• 避免栈溢出风险，尤其在大数据量下树高可达 ~30 层，但循环更轻量
• 每轮只做一次比较+一次可能交换，控制流清晰，JVM 易优化
• 位运算（如 >>）替代除法，提升索引计算效率
• 整个过程不创建新对象、不依赖指针，纯数组 + 索引算术，内存友好