眠子子子1. 堆结构：PriorityQueue的基石
PriorityQueue（优先队列）是计算机科学中一种重要的抽象数据类型，它不同于普通的先进先出(FIFO)队列，而是按照元素的优先级进行出队操作。这种特性使其在任务调度、图算法（如Dijkstra最短路径算法）、数据压缩（如Huffman编码）等场景中发挥着关键作用。
1.1 堆的本质与特性
堆(Heap)是一种特殊的完全二叉树，它满足以下性质：
- 结构性：除了最后一层，其他层都是完全填满的
- 堆序性：对于最大堆，每个节点的值都大于或等于其子节点的值；对于最小堆则相反
这种结构特性使得堆能够高效地维护元素的优先级关系。以最大堆为例，根节点始终是堆中的最大元素，这使得获取最高优先级元素的操作可以在O(1)时间内完成。
注意：完全二叉树的性质使得堆可以用数组高效实现，避免了指针存储的开销。对于索引为i的节点：
- 父节点索引：(i-1)/2
- 左子节点：2i+1
- 右子节点：2i+2
1.2 堆的操作复杂度分析
堆的核心操作及其时间复杂度如下：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 插入(offer) | O(log n) | 需要从下往上调整堆结构 |
| 删除(poll) | O(log n) | 需要从上往下调整堆结构 |
| 查看(peek) | O(1) | 直接返回堆顶元素 |
| 构建堆 | O(n) | 弗洛伊德算法从最后一个非叶子节点开始调整 |
这个效率表现使得堆成为实现优先队列的理想选择。相比之下，如果使用有序数组实现优先队列，虽然peek操作也是O(1)，但插入操作会退化为O(n)。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. PriorityQueue的实现原理
2.1 Java中的PriorityQueue剖析
Java标准库中的PriorityQueue类是基于堆实现的。我们来看其关键实现细节：
java复制// 存储元素的数组
transient Object[] queue;
// 默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 比较器，决定元素的优先级顺序
private final Comparator<? super E> comparator;
插入元素时的堆调整过程：
java复制public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1); // 自动扩容
siftUp(i, e); // 上浮操作
size = i + 1;
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
删除元素时的堆调整：
java复制public E poll() {