一、基本定义与特性
- 本质：
PriorityQueue是 Java 集合框架中Queue接口的实现类，基于**堆（Heap）**数据结构实现（默认是最小堆），底层通过数组存储元素。 - 核心特性：
- 队列中的元素会按照优先级顺序出队，而非先进先出（FIFO）；
- 不允许存储
null元素； - 非线程安全，多线程场景需使用
PriorityBlockingQueue； - 容量可自动扩容（默认初始容量为 11，扩容规则：容量 < 64 时翻倍，≥64 时扩容 50%）；
- 迭代器遍历的结果不保证有序，仅出队（
poll()/remove()）时保证优先级顺序。
二、关于堆
| 堆的核心维度 | 具体内容 |
|---|---|
| 定义 | 完全二叉树结构，满足'堆序性'：最小堆：任意节点值 ≤ 其子节点值（根节点为全局最小值）；最大堆：任意节点值 ≥ 其子节点值（根节点为全局最大值）。 |
| 存储结构 | 基于数组实现（利用完全二叉树的特性）：根节点：数组索引 0；索引 i 的节点 → 左子节点 2i+1、右子节点 2i+2、父节点 (i-1)/2（整数除法）；无需连续存储空节点，空间利用率高。 |
| 核心操作 | 1. 插入（siftUp / 向上调整）：新元素插入数组尾部，从下往上对比父节点，不满足堆序性则交换，直到堆序性恢复（时间复杂度 O(log n)）；2. 删除堆顶（siftDown / 向下调整）：移除根节点，将数组最后一个元素移到根节点，从上往下对比子节点，不满足堆序性则交换（选更小/更大的子节点），直到堆序性恢复（时间复杂度 O(log n)）；3. 堆化（heapify）：将无序数组转换为堆结构，从最后一个非叶子节点（索引 size/2 - 1）开始，逐个执行 siftDown（时间复杂度 O(n)）。 |
| 特性 | - 仅能高效获取/删除堆顶元素（优先级最高）；- 遍历无序（完全二叉树的特性决定，仅堆顶有序）；- 支持动态扩容（数组满时扩容，规则由实现决定）。 |
1. 优先级规则 ↔ 堆的类型
- PriorityQueue默认实现最小堆：依赖元素的
Comparable接口（compareTo()定义自然顺序），本质是维护最小堆的堆序性； - 自定义优先级（如最大堆）：传入
Comparator比较器，本质是修改堆的'堆序性判断逻辑'，例如：
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
- 异常根源：若元素未实现
Comparable且无Comparator，堆序性无法判断，运行时抛ClassCastException。
2. 存储结构 ↔ 堆的数组存储
- PriorityQueue 底层直接复用堆的数组存储逻辑：
- 初始容量 11（数组初始长度），扩容规则：容量 < 64 时翻倍，≥64 时扩容 50%（堆的数组存储需要连续空间，扩容是为了满足堆的动态插入）；
