17370845950

PriorityQueue的优先级由Comparator或元素自然顺序决定，底层用数组实现完全二叉堆，仅根节点保证最优，不维护整体有序。

PriorityQueue 的优先级由 Comparator 或自然顺序决定

Java 中 PriorityQueue 默认不是按插入顺序，也不是按“数值大小”自动理解优先级——它依赖 Comparator 实现或元素自身的 Comparable 接口。没有实现 Comparable 且未传入 Comparator，构造时不会报错，但首次调用 offer() 或 poll() 就会抛 ClassCastException。

• 使用自然顺序：元素类必须实现 Comparable，比如 Integer、String 可直接用
• 自定义顺序：构造时传入 Comparator，例如 new PriorityQueue((a, b) -> b - a) 构建大顶堆
• 注意 Comparator 返回值逻辑：负数表示 a 优先于 b（小顶堆默认行为），0 表示相等，正数表示 b 更优先

PriorityQueue 底层不是二叉搜索树，而是数组模拟的完全二叉堆

PriorityQueue 内部用动态数组（Object[] queue）存储元素，按完全二叉树层级遍历顺序存放。索引关系固定：
– 父节点索引 = (i - 1) / 2
– 左子节点索引 = 2 * i + 1
– 右子节点索引 = 2 * i + 2

• 堆化操作（如 offer() 后上浮、poll() 后下沉）只保证根最小（或按 Comparator 定义的“最小”），不保证左右子树有序
• 因此不能通过遍历数组获取排序结果；想全量有序，必须反复 poll() 或转成数组后调用 Arrays.sort()
• 初始容量为 11，扩容策略是 oldCapacity + (oldCapacity （即 ×1.5），非 2 的幂次，别误以为是类似 HashMap 的桶结构

常见误用：以为 peek() / poll() 能反映插入顺序或稳定排序

PriorityQueue 不保证相同优先级元素的处理顺序（即不稳定），也不保留插入时间信息。即使两个元素比较结果为 0，它们谁先被 poll() 出来是不确定的。

• 若需稳定优先队列（相同优先级时按插入先后出队），得手动封装：例如用 long sequenceId 辅助比较
• peek() 只返回头元素，不移除；poll() 移除并返回；remove(Object) 时间复杂度是 O(n)，慎用
• 遍历时（如增强 for 循环）不按优先级顺序，而是按底层数组当前排列——这和堆逻辑无关，纯属内部存储快照，不可依赖

性能与线程安全的关键事实

PriorityQueue 是非线程安全的。多线程环境下直接共享实例，会导致 offer()/poll() 出现数据错乱甚至无限循环（因堆结构被并发修改破坏）。

• 单线程场景下，offer() 和 poll() 均为 O(log n)，peek() 是 O(1)
• 不要用 Collections.synchronizedCollection(new PriorityQueue()) —— 这仅同步单个操作，无法保证复合操作（如先 isEmpty() 再 poll()）的原子性
• 真需要并发优先队列，用 PriorityBlockingQueue；它基于可重入锁 + 条件队列，支持阻塞，但依然不保证公平性

PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(4);
System.out.println(maxHeap.poll()); // 输出 4
System.out.println(maxHeap.poll()); // 输出 3

堆结构本身不暴露，所有逻辑都封装在 siftUp() 和 siftDown() 方法里。真正容易被忽略的是：你看到的“顺序”，永远只在取的时候才被强制维持；存进去那一刻，数组里根本看不出优先级。