堆排序的核心思想是利用堆这种完全二叉树结构，通过建堆和反复调整堆的操作来实现元素的有序管理，Java中的PriorityQueue正是基于这一思想实现的优先队列，它能够在元素插入和移除的过程中自动维护内部元素的有序状态，默认情况下是小顶堆结构，也就是堆顶元素是最小的元素。
PriorityQueue的底层存储结构
PriorityQueue的底层并没有使用复杂的树节点结构，而是采用了一个Object类型的数组来存储堆中的元素，这个数组的逻辑结构是一棵完全二叉树。对于数组中任意索引为i的元素，它的左子节点索引为2*i+1，右子节点索引为2*i+2，父节点索引为(i-1)/2，这种映射关系让数组可以完美模拟完全二叉树的特性，也为堆排序的相关操作提供了便利。
PriorityQueue内部维护了一个比较器Comparator，如果没有指定比较器，就会使用元素的自然排序，也就是元素需要实现Comparable接口，比较规则决定了堆的类型，比如自然排序中compareTo方法返回负数表示当前元素更小，此时构建的是小顶堆，反之如果自定义比较器让大的元素排在前面，就会构建大顶堆。
元素入队时的堆调整过程
当我们调用PriorityQueue的offer方法插入元素时，底层会先检查数组是否需要扩容，如果不需要扩容，就会将新元素放到数组的末尾，也就是完全二叉树的最后一个位置，然后执行上浮操作，也就是siftUp方法，这个过程就是堆排序中调整堆的核心步骤之一。
上浮操作的逻辑是：将新插入的节点和它的父节点进行比较，如果不符合堆的排序规则，就交换两个节点的位置，然后继续向上和新的父节点比较，直到符合规则或者到达堆顶为止。如果是小顶堆，当子节点的值小于父节点的值时就会交换，这样就能保证堆顶始终是最小的元素。
以下是PriorityQueue中siftUp方法的简化实现逻辑，这里以小顶堆为例：
private void siftUp(int k, Object x) {
// k是新元素的初始索引，也就是数组末尾的位置
while (k > 0) {
// 计算父节点索引
int parent = (k - 1) >>> 1;
Object e = queue[parent];
// 如果新元素大于等于父节点，符合小顶堆规则，停止上浮
if (comparator != null) {
if (comparator.compare(x, e) >= 0) {
break;
}
} else {
// 使用自然排序，假设元素实现了Comparable接口
Comparable<? super T> key = (Comparable<? super T>) x;
if (key.compareTo((T) e) >= 0) {
break;
}
}
// 不符合规则，交换父节点和当前节点的位置
queue[k] = e;
k = parent;
}
// 将新元素放到最终的位置
queue[k] = x;
}
元素出队时的堆调整过程
当调用PriorityQueue的poll方法移除堆顶元素时，底层会先取出数组的第一个元素作为返回值，然后将数组的最后一个元素放到堆顶的位置，也就是索引0的位置，之后执行下沉操作，也就是siftDown方法，这个操作同样是堆排序中调整堆的核心步骤。
下沉操作的逻辑是：从堆顶节点开始，比较它和两个子节点的大小，如果不符合堆的排序规则，就和更小的那个子节点（小顶堆场景）交换位置，然后继续向下比较，直到符合规则或者没有子节点为止。这个过程会把原来的最后一个元素调整到合适的位置，重新维持堆的有序结构。
以下是siftDown方法的简化实现逻辑：
private void siftDown(int k, Object x) {
// k是要调整的节点的初始索引，出队时初始是0
int half = size >>> 1;
while (k < half) {
// 计算左子节点索引
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
// 找出左右子节点中更小的那个（小顶堆场景）
if (right < size) {
if (comparator != null) {
if (comparator.compare(c, queue[right]) > 0) {
c = queue[child = right];
}
} else {
Comparable<? super T> key = (Comparable<? super T>) c;
if (key.compareTo((T) queue[right]) > 0) {
c = queue[child = right];
}
}
}
// 如果当前节点已经比更小的子节点还小，符合规则，停止下沉
if (comparator != null) {
if (comparator.compare(x, c) <= 0) {
break;
}
} else {
Comparable<? super T> key = (Comparable<? super T>) x;
if (key.compareTo((T) c) <= 0) {
break;
}
}
// 不符合规则，交换当前节点和子节点的位置
queue[k] = c;
k = child;
}
// 将待调整的元素放到最终位置
queue[k] = x;
}
初始化时的建堆过程
当通过构造函数传入一个集合来初始化PriorityQueue时，底层会先把这个集合的元素全部放到数组中，然后调用heapify方法进行建堆，这个过程是堆排序的建堆步骤，会从最后一个非叶子节点开始，依次向前对每个节点执行下沉操作，这样就能把整个无序的数组调整为一个符合规则的堆结构。
最后一个非叶子节点的索引是(size >>> 1) - 1，因为完全二叉树的叶子节点都是从索引size/2开始的位置，所以从最后一个非叶子节点开始向前调整，能保证每个子树都符合堆的规则，最终整个树就会成为合法的堆。
扩容机制对堆结构的影响
PriorityQueue的数组扩容不会破坏堆的结构，因为扩容只是创建了一个更大的数组，然后把原来数组中的所有元素复制到新数组中，数组的元素顺序没有发生变化，而堆的逻辑结构是基于数组索引的映射关系，只要元素顺序不变，堆的逻辑结构就不会被破坏，扩容之后只需要继续按照原来的规则进行元素的插入和移除操作即可。
扩容的触发时机是当数组中元素的个数达到数组长度时，默认情况下新数组的长度是原来长度的2倍，如果原来长度小于64，会先扩容到原来的2倍加2，这个机制和ArrayList的扩容逻辑类似，但是不会影响堆的有序性。
总结
PriorityQueue通过数组存储元素，利用完全二叉树的索引映射关系模拟堆结构，在元素入队时通过上浮操作调整堆，出队时通过下沉操作调整堆，初始化时通过建堆操作构建初始堆，整个过程完全基于堆排序的核心思想。这种实现方式让PriorityQueue的入队和出队操作的时间复杂度都是O(log n)，能够高效地维护元素的有序状态，适合需要频繁获取最值或者按顺序处理元素的场景。
堆排序PriorityQueue优先队列数据结构修改时间：2026-06-14 12:39:42