编辑“︁优先队列基础”︁

{{DISPLAYTITLE:优先队列基础}}

'''优先队列'''（Priority Queue）是一种特殊的线性数据结构，其中每个元素都关联有一个优先级。与普通队列（FIFO）不同，优先队列中的元素按照优先级顺序出队，而不是按照插入顺序。优先队列在算法设计、任务调度、图算法（如Dijkstra算法）等领域有广泛应用。

== 基本概念 ==
优先队列支持以下核心操作：
* '''入队（Enqueue）'''：插入一个带有优先级的元素。
* '''出队（Dequeue）'''：移除并返回优先级最高（或最低）的元素。
* '''查看队首（Peek）'''：返回优先级最高（或最低）的元素，但不移除它。
* '''判空（IsEmpty）'''：检查队列是否为空。

优先队列的实现方式包括：
* 数组或链表（简单但效率低）
* 二叉堆（常用，时间复杂度优化）
* 斐波那契堆（高级场景）

== 实现示例 ==
以下是基于Python的二叉堆实现示例：

<syntaxhighlight lang="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}")
</syntaxhighlight>

'''输出结果：'''
<pre>
Executing Task 2 with priority 1
Executing Task 1 with priority 2
Executing Task 3 with priority 3
</pre>

== 时间复杂度分析 ==
不同实现方式的时间复杂度对比：

{| class="wikitable"
|+ 优先队列操作时间复杂度
! 实现方式 !! 入队 !! 出队 !! 查看队首
|-
| 无序数组/链表 || 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)
|}

== 可视化示例 ==
以下是最小堆的插入过程演示（数字代表优先级）：

<mermaid>
graph TD
    subgraph 初始状态
        A[2]
    end
    subgraph 插入1
        B[1] --> A[2]
    end
    subgraph 插入3
        C[1] --> D[2] --> E[3]
    end
</mermaid>

== 数学表示 ==
优先队列可以形式化定义为：
<math>
Q = \{(p_1, e_1), (p_2, e_2), ..., (p_n, e_n)\}
</math>
其中<math>p_i</math>是优先级，<math>e_i</math>是元素，满足：
<math>
\forall i \in [1, n-1], p_i \leq p_{i+1} \quad \text{(最小堆)}
</math>

== 实际应用案例 ==
1. '''医院急诊分诊'''：病人按病情严重程度（优先级）接受治疗
2. '''操作系统进程调度'''：高优先级任务优先获得CPU资源
3. '''路径查找算法'''：Dijkstra算法使用优先队列选择最短路径

== 高级主题 ==
* '''双端优先队列'''：支持高效获取最大和最小元素
* '''合并优先队列'''：高效合并两个优先队列的操作
* '''可更新优先队列'''：支持修改已有元素的优先级

== 常见问题 ==
'''Q：优先队列和普通队列有什么区别？'''
A：普通队列严格遵循FIFO原则，而优先队列根据优先级决定出队顺序。

'''Q：什么时候应该使用优先队列？'''
A：当处理需要按特定顺序（而非插入顺序）访问元素的场景时，如任务调度、带权图算法等。

'''Q：如何实现最大优先队列？'''
A：可以通过反转比较逻辑（最大堆）或在存储时取负值（最小堆变通）实现。Python示例：
<syntaxhighlight lang="python">
# 最大堆实现
heapq._heapify_max(priority_queue)  # 内部方法
# 或通过存储负值
heapq.heappush(priority_queue, (-priority, task))
</syntaxhighlight>

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]