Java PriorityQueue 与最小堆总结

最小堆概念

• 堆序性：每个父节点 ≤ 子节点（最小堆）

• 不保证兄弟节点大小关系

• 不保证中序遍历或层序遍历有序

• 核心作用：快速找到最小值（或最大堆则找到最大值）

• 实现方式：完全二叉树，用数组实现

  • 父节点索引 i
  • 左孩子索引 2*i + 1
  • 右孩子索引 2*i + 2
  • 父节点索引 (i - 1)/2

1️⃣ PriorityQueue 基础概念

• Java 中优先队列实现，底层基于堆（Heap），默认最小堆
• 元素可按照自然顺序或自定义比较器排序
• 插入和删除堆顶元素时间复杂度为 O(log n)
• 不保证相同优先级元素顺序

常用方法

2️⃣ 多条件排序示例

当需要根据多个条件排序时，例如虚拟机调度场景：

• 第一条件：可用内存大 → 小
• 第二条件：已部署虚拟机少 → 多
• 第三条件：编号小 → 大

PriorityQueue<Machine> pq = new PriorityQueue<>((a, b) -> {
    if (b.available != a.available) return b.available - a.available; // 内存大优先
    if (a.count != b.count) return a.count - b.count;               // 已部署少优先
    return a.id - b.id;                                             // 编号小优先
});

注意：多条件排序时先比较优先级最高的条件

3️⃣ 获取第二小或任意排序元素

• PriorityQueue 只能保证访问堆顶元素（最小或最大）

• 不能直接访问第二小/第二大元素

• 获取第二小元素方法：

  1. 弹出堆顶（poll()） → 新堆顶就是第二小元素
  2. 如果需要访问任意排序元素，可以将堆复制到数组再排序（O(n log n))
  3. 对于频繁访问第 k 小元素，可使用 TreeSet 或索引堆优化

总结：

• 最小堆核心保证：父节点 ≤ 子节点 → 堆顶为最小元素
• PriorityQueue 是最小堆/最大堆的封装，提供高效插入和删除堆顶操作
• 对于复杂排序，可使用自定义比较器实现多条件优先级
• 想获取第二小或第 k 小元素，需要额外操作，不能直接访问