优先队列基础
优先队列（Priority Queue）是一种特殊的线性数据结构，其中每个元素都关联有一个优先级。与普通队列（FIFO）不同，优先队列中的元素按照优先级顺序出队，而不是按照插入顺序。优先队列在算法设计、任务调度、图算法（如Dijkstra算法）等领域有广泛应用。
基本概念[编辑 | 编辑源代码]
优先队列支持以下核心操作：
- 入队（Enqueue）：插入一个带有优先级的元素。
- 出队（Dequeue）：移除并返回优先级最高（或最低）的元素。
- 查看队首（Peek）：返回优先级最高（或最低）的元素，但不移除它。
- 判空（IsEmpty）：检查队列是否为空。
优先队列的实现方式包括：
- 数组或链表（简单但效率低）
- 二叉堆（常用，时间复杂度优化）
- 斐波那契堆（高级场景）
实现示例[编辑 | 编辑源代码]
以下是基于Python的二叉堆实现示例：
import heapq
# 创建一个优先队列（最小堆）
priority_queue = []
# 入队操作（带优先级）
heapq.heappush(priority_queue, (2, "Task 1")) # 优先级为2
heapq.heappush(priority_queue, (1, "Task 2")) # 优先级为1
heapq.heappush(priority_queue, (3, "Task 3")) # 优先级为3
# 出队操作（按优先级顺序）
while priority_queue:
priority, task = heapq.heappop(priority_queue)
print(f"Executing {task} with priority {priority}")
输出结果：
Executing Task 2 with priority 1 Executing Task 1 with priority 2 Executing Task 3 with priority 3
时间复杂度分析[编辑 | 编辑源代码]
不同实现方式的时间复杂度对比：
| 实现方式 | 入队 | 出队 | 查看队首 |
|---|---|---|---|
| 无序数组/链表 | O(1) | O(n) | O(n) |
| 有序数组/链表 | O(n) | O(1) | O(1) |
| 二叉堆 | O(log n) | O(log n) | O(1) |
| 斐波那契堆 | O(1) | O(log n) | O(1) |
可视化示例[编辑 | 编辑源代码]
以下是最小堆的插入过程演示（数字代表优先级）：
数学表示[编辑 | 编辑源代码]
优先队列可以形式化定义为： 其中是优先级，是元素，满足：
实际应用案例[编辑 | 编辑源代码]
1. 医院急诊分诊：病人按病情严重程度（优先级）接受治疗 2. 操作系统进程调度：高优先级任务优先获得CPU资源 3. 路径查找算法：Dijkstra算法使用优先队列选择最短路径
高级主题[编辑 | 编辑源代码]
- 双端优先队列：支持高效获取最大和最小元素
- 合并优先队列：高效合并两个优先队列的操作
- 可更新优先队列：支持修改已有元素的优先级
常见问题[编辑 | 编辑源代码]
Q：优先队列和普通队列有什么区别？ A：普通队列严格遵循FIFO原则，而优先队列根据优先级决定出队顺序。
Q：什么时候应该使用优先队列？ A：当处理需要按特定顺序（而非插入顺序）访问元素的场景时，如任务调度、带权图算法等。
Q：如何实现最大优先队列？ A：可以通过反转比较逻辑（最大堆）或在存储时取负值（最小堆变通）实现。Python示例：
# 最大堆实现
heapq._heapify_max(priority_queue) # 内部方法
# 或通过存储负值
heapq.heappush(priority_queue, (-priority, task))