目录
一、从生活场景理解优先级队列
1.1 为什么需要优先级队列？
回想一下我们之前学过的普通队列（Queue），它的规则是先进先出（FIFO）。但在现实世界中，很多事情并不按先来后到的顺序处理：
-
手机来电打断游戏：你在打游戏时接到电话，系统应该优先处理来电，而不是等你打完这局
-
医院急诊分诊：危重病人优先就诊，而不是按挂号顺序
-
操作系统进程调度：高优先级的进程先获得CPU资源
-
班主任排座位：成绩好的同学可以先挑选座位
这些场景的共同点是：数据带有优先级，优先级高的先被处理。这就是优先级队列（Priority Queue）诞生的原因。
1.2 优先级队列的核心操作
优先级队列只需要支持两个最基本的操作：
| 操作 | 功能 | 时间复杂度 |
|---|---|---|
|
| 插入一个新元素 | O(log n) |
|
| 删除并返回优先级最高的元素 | O(log n) |
|
| 查看优先级最高的元素（不删除） | O(1) |
二、堆：优先级队列的底层实现
2.1 什么是堆？
Java中的PriorityQueue底层使用的是堆这种数据结构。堆本质上是一棵完全二叉树，同时满足以下性质：
堆的性质：
-
堆中某个节点的值总是不大于或不小于其父节点的值
-
堆总是一棵完全二叉树
根据第一条性质的不同，堆分为两种：
| 类型 | 条件 | 特点 |
|---|---|---|
| 小根堆（最小堆） | 父节点 ≤ 子节点 | 根节点是最小值 |
| 大根堆（最大堆） | 父节点 ≥ 子节点 | 根节点是最大值 |
2.2 堆的存储方式
由于堆是完全二叉树，我们可以用数组来高效存储。不需要像普通二叉树那样用链式存储，省去了左右指针的空间。
数组存储的映射规则：
假设节点在数组中的下标为i：
-
父节点下标：
(i - 1) / 2（当i > 0时） -
左孩子下标：
2 * i + 1（如果存在） -
右孩子下标：
2 * i + 2（如果存在）
数组：[27, 15, 19, 18, 28, 34, 65, 49, 25, 37]
对应完全二叉树：
27
/ \
15 19
/ \ / \
18 28 34 65
/\ /
49 25 37为什么非完全二叉树不适合数组存储？
因为需要留出空位来保持完全二叉树的形状，会造成大量空间浪费。
2.3 堆的核心操作：向下调整
向下调整是堆最核心的操作。它的前提条件是：根节点的左右子树都已经满足堆的性质，只有根节点不满足。
以小根堆为例，向下调整的步骤：
-
用
parent标记需要调整的节点，child标记其左孩子 -
如果右孩子存在且比左孩子小，
child改为右孩子（找到最小的孩子） -
比较
parent和child：-
如果
parent≤child，调整结束 -
否则，交换
parent和child，然后继续向下调整
-
/**
* 向下调整（小根堆）
* @param array 存储堆的数组
* @param parent 需要调整的父节点下标
*/
public void shiftDown(int[] array, int parent) {
int child = 2 * parent + 1; // 左孩子
int size = array.length;
while (child < size) {
// 如果右孩子存在且更小，选择右孩子
if (child + 1 < size && array[child + 1] < array[child]) {
child += 1;
}
// 如果父节点比最小的孩子还小，调整结束
if (array[parent] <= array[child]) {
break;
}
// 交换父节点和较小的孩子
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;
// 继续向下调整
parent = child;
child = 2 * parent + 1;
}
}时间复杂度：最坏情况下从根节点一直调整到叶子节点，比较次数等于树的高度，即 O(log n)。
2.4 建堆：从无序数组到堆
如果整个数组都不满足堆的性质怎么办？我们需要从最后一个非叶子节点开始，从下往上依次对每个节点进行向下调整。
最后一个非叶子节点的下标：(size - 1 - 1) / 2 = size / 2 - 1
/**
* 建堆（小根堆）
* @param array 待调整的数组
*/
public void createHeap(int[] array) {
// 从最后一个非叶子节点开始，从下往上调整
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
shiftDown(array, parent);
}
}建堆的时间复杂度是多少？
直觉上可能会认为是 O(n log n)，但实际上经过数学推导，建堆的时间复杂度是 O(n)。
推导过程简要说明：
假设树的高度为h，各层节点数和需要移动的层数如下：
-
第1层：2⁰个节点，需要移动h-1层
-
第2层：2¹个节点，需要移动h-2层
-
...
-
第h-1层：2ʰ⁻²个节点，需要移动1层
经过错位相减求和，得到总移动次数 T(n) = n - log₂(n+1) ≈ n。
所以建堆的时间复杂度为 O(n)。
2.5 堆的插入：向上调整
插入新元素时，先把元素放到数组末尾，然后进行向上调整。
/**
* 向上调整（小根堆）
* @param child 新插入的孩子节点下标
*/
public void shiftUp(int child) {
int parent = (child - 1) / 2;
while (child > 0) {
// 如果父节点比孩子小，调整结束
if (array[parent] <= array[child]) {
break;
}
// 交换父节点和孩子
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;
// 继续向上调整
child = parent;
parent = (child - 1) / 2;
}
}2.6 堆的删除：删除堆顶元素
堆的删除一定是删除堆顶元素（优先级最高的元素）。步骤如下：
-
将堆顶元素与最后一个元素交换
-
有效元素个数减1
-
对新的堆顶元素进行向下调整
public int poll() {
int oldValue = array[0];
array[0] = array[--size]; // 将最后一个元素放到堆顶
shiftDown(0); // 向下调整
return oldValue;
}三、用堆模拟实现优先级队列
把上面学的知识整合起来，我们可以自己实现一个简化的优先级队列：
public class MyPriorityQueue {
private int[] array;
private int size;
public MyPriorityQueue() {
array = new int[100]; // 简化实现，不考虑扩容
size = 0;
}
// 插入元素
public void offer(int e) {
array[size++] = e;
shiftUp(size - 1);
}
// 删除堆顶元素
public int poll() {
int oldValue = array[0];
array[0] = array[--size];
shiftDown(0);
return oldValue;
}
// 查看堆顶元素
public int peek() {
return array[0];
}
// 向下调整
private void shiftDown(int parent) {
int child = 2 * parent + 1;
while (child < size) {
if (child + 1 < size && array[child + 1] < array[child]) {
child += 1;
}
if (array[parent] <= array[child]) {
break;
}
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;
parent = child;
child = 2 * parent + 1;
}
}
// 向上调整
private void shiftUp(int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (array[parent] <= array[child]) {
break;
}
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;
child = parent;
parent = (child - 1) / 2;
}
}
}四、Java中的PriorityQueue
4.1 基本特性
Java集合框架中提供了PriorityQueue类，使用时需要导入：
import java.util.PriorityQueue;使用注意事项：
-
放置的元素必须能比较大小，否则抛出
ClassCastException -
不能插入null对象，否则抛出
NullPointerException -
没有容量限制，内部可以自动扩容
-
插入和删除的时间复杂度为 O(log n)
-
默认是小根堆（最小值优先）
4.2 三种构造方式
// 方式一：无参构造，默认容量为11
PriorityQueue<Integer> q1 = new PriorityQueue<>();
// 方式二：指定初始容量
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
// 方式三：用已有集合构造
ArrayList<Integer> list = new ArrayList<>();
list.add(4);
list.add(3);
list.add(2);
list.add(1);
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
System.out.println(q3.peek()); // 输出1（最小值）4.3 核心方法
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 插入元素
pq.offer(5);
pq.offer(1);
pq.offer(9);
pq.offer(2);
pq.offer(8);
System.out.println(pq.size()); // 5
// 获取最小值（不删除）
System.out.println(pq.peek()); // 1
// 删除最小值
System.out.println(pq.poll()); // 1
System.out.println(pq.poll()); // 2
System.out.println(pq.size()); // 3
// 清空
pq.clear();
System.out.println(pq.isEmpty()); // true4.4 如何创建大根堆？
默认是小根堆，如果需要大根堆，需要传入自定义的比较器：
// 自定义比较器，让大的元素优先级更高
class IntCmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1; // 降序排列
}
}
// 创建大根堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new IntCmp());
maxHeap.offer(4);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(1);
maxHeap.offer(5);
System.out.println(maxHeap.peek()); // 输出5（最大值）4.5 扩容机制
PriorityQueue的扩容规则如下：
-
如果容量小于64时，按 2倍 扩容
-
如果容量大于等于64时，按 1.5倍 扩容
-
如果容量超过
MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8），按MAX_ARRAY_SIZE扩容
五、堆的两大经典应用
5.1 堆排序
堆排序利用堆的思想进行排序，分为两步：
-
建堆：
-
升序 → 建大根堆
-
降序 → 建小根堆
-
-
利用堆删除思想排序：
-
每次将堆顶元素与最后一个元素交换
-
有效元素个数减1
-
对新的堆顶进行向下调整
-
public void heapSort(int[] array) {
// 1. 建大根堆（升序）
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
shiftDownForSort(array, array.length, parent);
}
// 2. 排序
int end = array.length - 1;
while (end > 0) {
// 交换堆顶和最后一个元素
int temp = array[0];
array[0] = array[end];
array[end] = temp;
// 对新的堆顶进行向下调整
shiftDownForSort(array, end, 0);
end--;
}
}
private void shiftDownForSort(int[] array, int size, int parent) {
int child = 2 * parent + 1;
while (child < size) {
if (child + 1 < size && array[child + 1] > array[child]) {
child += 1;
}
if (array[parent] >= array[child]) {
break;
}
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;
parent = child;
child = 2 * parent + 1;
}
}堆排序的时间复杂度：O(n log n)
5.2 Top-K问题
问题：从海量数据中找出前K个最大（或最小）的元素。
传统思路：对所有数据排序，取前K个。但如果数据量很大（比如10亿条），排序就不现实了。
堆的解法：
以求前K个最大元素为例：
-
先用前K个元素建一个小根堆
-
遍历剩下的N-K个元素，每个元素与堆顶比较：
-
如果比堆顶大，替换堆顶，然后向下调整
-
-
遍历结束后，堆中的K个元素就是前K个最大的
public int[] topK(int[] array, int k) {
// 1. 用前K个元素建小根堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int i = 0; i < k; i++) {
minHeap.offer(array[i]);
}
// 2. 遍历剩余元素
for (int i = k; i < array.length; i++) {
int top = minHeap.peek();
if (array[i] > top) {
minHeap.poll();
minHeap.offer(array[i]);
}
}
// 3. 收集结果
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = minHeap.poll();
}
return result;
}为什么用小根堆找最大？
因为小根堆的堆顶是堆中最小的元素。如果新元素比堆顶大，说明它比当前最小的候选者大，可以入选。这样堆中始终保存着当前已遍历数据中最大的K个。
同理：求前K个最小的元素，用大根堆。
时间复杂度：O(n log k)，当k远小于n时，接近O(n)
六、常见面试题
题目1：判断是否为堆
下列关键字序列为堆的是：（ ）
A: 100, 60, 70, 50, 32, 65
B: 60, 70, 65, 50, 32, 100
C: 65, 100, 70, 32, 50, 60
D: 70, 65, 100, 32, 50, 60
E: 32, 50, 100, 70, 65, 60
F: 50, 100, 70, 65, 60, 32
解答：把数组还原为完全二叉树，检查每个父节点是否满足堆的性质。
选项A：100 > 60且100 > 70，60 > 50且60 > 32，70 > 65。每个父节点都大于子节点，是大根堆。✅
答案：A
题目2：堆删除后的比较次数
已知小根堆为8, 15, 10, 21, 34, 16, 12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是：（ ）
A: 1
B: 2
C: 3
D: 4
解答：删除8后，将12放到堆顶，然后向下调整。12先与15和10比较（找到较小的10），交换；再与16和12比较（12已经是叶子），结束。共比较3次。
答案：C
七、总结与学习建议
7.1 核心要点回顾
| 知识点 | 关键内容 |
|---|---|
| 堆的定义 | 完全二叉树 + 父节点与子节点的大小关系 |
| 小根堆 | 父节点 ≤ 子节点，根节点最小 |
| 大根堆 | 父节点 ≥ 子节点，根节点最大 |
| 向下调整 | 前提：左右子树已是堆，时间复杂度O(log n) |
| 建堆 | 从最后一个非叶子节点开始调整，时间复杂度O(n) |
| 插入 | 先放末尾，再向上调整 |
| 删除 | 交换堆顶和末尾，再向下调整 |
| PriorityQueue | 默认小根堆，可通过Comparator改为大根堆 |
| 堆排序 | 升序建大堆，降序建小堆，时间复杂度O(n log n) |
| Top-K | 找最大K个用小堆，找最小K个用大堆 |
7.2 学习建议
-
画图理解：堆的调整过程非常适合用画图来理解，建议在纸上画出每一步的变化
-
手写代码：自己实现一遍向下调整、建堆、堆排序，加深印象
-
对比记忆：对比小根堆和大根堆的异同，对比PriorityQueue和普通Queue的区别
-
刷题练习：在LeetCode上搜索"heap"或"priority queue"标签
7.3 推荐练习题目
-
LeetCode 215：数组中的第K个最大元素
-
LeetCode 347：前K个高频元素
-
LeetCode 373：查找和最小的K对数字
-
LeetCode 703：数据流中的第K大元素
如果你觉得这篇文章对你有帮助，欢迎点赞收藏。下一篇我们将深入Java集合框架的更多内容，敬请期待！
注：本文为个人学习总结，所有代码示例均为独立编写。建议读者在学习过程中结合JDK官方文档和源码进行验证。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2401_87122037/article/details/163002025
