数据结构与算法 / 系统课时
优先队列
优先队列
优先队列并不按进入顺序取出元素,而是始终先处理优先级最高的元素。本课使用最大堆实现插入、查看最高优先级和删除最高优先级三种操作,并验证每次调整后堆序性质仍然成立。
学习目标
- 理解优先队列与普通队列的区别,以及最大堆为何适合作为底层结构。
- 掌握
offer、peek和poll的实现过程。 - 能够分析三种操作的时间复杂度与空队列边界。
核心原理
最大堆是一棵完全二叉树,任意父节点都不小于它的孩子。用数组保存时,下标 i 的父节点为 (i - 1) / 2,左孩子为 2 * i + 1,右孩子为 2 * i + 2。
插入元素时,先把新值放到数组末尾,再不断与父节点比较并向上交换,这个过程称为上浮。删除最高优先级元素时,先保存根节点,再把末尾元素移到根位置,删除末尾槽位,最后让新根与较大的孩子交换并向下移动,这个过程称为下沉。

优先队列的三个核心操作具有不同职责:
| 操作 | 作用 | 最大堆中的位置 | 时间复杂度 |
|---|---|---|---|
offer(value) |
插入新元素 | 末尾写入后上浮 | |
peek() |
查看最高优先级元素 | 读取根节点 | |
poll() |
删除并返回最高优先级元素 | 根节点替换后下沉 |
完整可运行示例
下面的 Java 17 程序实现一个整数最大优先队列。ArrayList 只负责动态存储,优先级顺序完全由上浮和下沉逻辑维护。
java
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class MaxPriorityQueueDemo {
static class MaxPriorityQueue {
private final List<Integer> heap = new ArrayList<>();
public void offer(int value) {
heap.add(value);
siftUp(heap.size() - 1);
}
public int peek() {
ensureNotEmpty();
return heap.get(0);
}
public int poll() {
ensureNotEmpty();
int result = heap.get(0);
int lastValue = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heap.set(0, lastValue);
siftDown(0);
}
return result;
}
public boolean isEmpty() {
return heap.isEmpty();
}
private void siftUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap.get(parent) >= heap.get(index)) {
break;
}
swap(parent, index);
index = parent;
}
}
private void siftDown(int index) {
int size = heap.size();
while (true) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
if (left < size && heap.get(left) > heap.get(largest)) {
largest = left;
}
if (right < size && heap.get(right) > heap.get(largest)) {
largest = right;
}
if (largest == index) {
break;
}
swap(index, largest);
index = largest;
}
}
private void swap(int first, int second) {
int temporary = heap.get(first);
heap.set(first, heap.get(second));
heap.set(second, temporary);
}
private void ensureNotEmpty() {
if (heap.isEmpty()) {
throw new NoSuchElementException("优先队列为空");
}
}
@Override
public String toString() {
return heap.toString();
}
}
public static void main(String[] args) {
MaxPriorityQueue queue = new MaxPriorityQueue();
for (int value : new int[] {4, 10, 7, 3}) {
queue.offer(value);
}
System.out.println("堆数组: " + queue);
System.out.println("最高优先级: " + queue.peek());
System.out.println("删除最高优先级: " + queue.poll());
System.out.println("删除后的堆: " + queue);
while (!queue.isEmpty()) {
System.out.println("继续删除: " + queue.poll());
}
}
}将代码保存为 MaxPriorityQueueDemo.java,然后运行:
bash
javac MaxPriorityQueueDemo.java
java MaxPriorityQueueDemo预期输出:
text
堆数组: [10, 4, 7, 3]
最高优先级: 10
删除最高优先级: 10
删除后的堆: [7, 4, 3]
继续删除: 7
继续删除: 4
继续删除: 3复杂度与边界
堆中从叶子到根的高度为 ,所以上浮和下沉最多经过一条根到叶子的路径。底层数组占用 空间,操作本身只使用常数个临时变量。
调用 peek() 或 poll() 前必须处理空队列。示例选择抛出 NoSuchElementException,工程中也可以返回 OptionalInt,但不要用特殊整数表示“空”,否则该整数可能与合法优先级冲突。
优先队列只保证根节点是当前最大值,不保证整个数组全局有序。若业务需要稳定处理相同优先级,可把“优先级”和“入队序号”组成复合比较键。
本课总结
- 最大堆通过“父节点不小于孩子”保证根节点始终具有最高优先级。
- 插入依靠上浮,删除根节点依靠末尾替换与下沉,两者复杂度均为 。
peek()只读取根节点,因此是 ,但必须显式处理空队列。
下一课预告
下一课将学习“并查集基础”,掌握创建集合、查找代表元和合并集合三个操作,并理解它们如何高效维护动态连通关系。
按自己的节奏,确认真正理解。