第 3.10.4 章：优先级队列 (Priority Queues)

欢迎来到进阶数据结构部分！你已经熟练掌握了栈 (Stack, LIFO) 和标准队列 (Queue, FIFO)。现在，我们要接触一种不关心“到达先后”，只关心“重要程度”的结构，这就是优先级队列 (Priority Queue)。

理解优先级队列至关重要，因为它们是许多复杂算法的基础，广泛应用于路由选择、任务调度及高效的数据处理中。

1. 什么是优先级队列？

优先级队列是一种进阶数据结构，其中元素移除的顺序完全取决于元素的优先级 (Priority)，而不是到达的时间。

它虽然也是一种队列，但完全打破了“先进先出 (FIFO)”的原则。

类比：医院急诊室（分诊制度）

想象你来到急诊室。医生不会因为你来得早先为你治疗，而是由分诊护士评估你的情况并指定优先级：

  • 患者 1（9:00 到达）- 脚趾骨折（低优先级：3）
  • 患者 2（9:15 到达）- 胸痛（高优先级：1）
  • 患者 3（9:30 到达）- 轻微烫伤（中优先级：2）

即使患者 1 先到达，患者 2（优先级 1）也会排在所有人前面被接诊。优先级队列确保了最紧急的情况总是被优先处理。

核心规则：优先级最高的元素总是会被最先检索（出队）的元素。

注：如果两个项目的优先级相同，它们通常会按照标准 FIFO 规则处理。

快速回顾：

标准队列：先进先出 (FIFO)。

优先级队列：最高优先级先出 (HPIFO)。

2. 优先级队列的操作

与标准队列类似，核心操作是添加元素（入队）和移除元素（出队）。

2.1. 添加元素 (Enqueue)

当你入队 (enqueue)一个元素时，必须为其关联一个优先级值。它在底层结构（如数组）中的存储位置，取决于你为了维护优先级顺序而设计的实现方式。

示例：入队 (项目: "发送邮件", 优先级: 5)

2.2. 移除元素 (Dequeue)

出队 (dequeue)操作会移除并返回当前具有最高优先级的元素。

示例：如果项目“系统关键警报”的优先级为 10，且没有其他项目的优先级为 10，则无论该项目何时被添加，它都会被优先出队。

3. 使用一维数组实现

课程大纲要求我们理解如何使用一维数组来实现优先级队列。

由于数组本身并不具备“优先级”概念，我们必须创建一套结构或规则，将优先级逻辑施加于数组存储之上。

设计决策：如何存储数据？

当使用数组来实现优先级队列时，处理数据与优先级配对主要有两种方式：

方案 1：无序数组（入队简单，出队较慢）

元素直接添加到数组的下一个可用位置（类似于标准线性队列）。这种方式非常快，时间复杂度为 O(1)。

  • 入队：添加到末尾。
  • 出队：为了移除最高优先级元素，算法必须遍历整个数组以找到优先级最高的项目。这比较慢，时间复杂度为 O(n)，其中 \(n\) 为元素个数。

方案 2：有序数组（入队较慢，出队较快）

元素在插入时即按优先级排序（例如，优先级最高的项目始终处于索引 0）。这是在检索效率至关重要时的常用方法。

  • 入队（添加）：当新项目到达时，必须根据其优先级找到正确位置，并将所有优先级较低的元素后移以腾出空间。这可能较慢，时间复杂度为 O(n)。
  • 出队（移除）：最高优先级元素始终固定在数组前端（索引 0）。移除操作非常快，时间复杂度为 O(1)。

如果一开始觉得难以理解也不用担心！核心概念就是管理数组指针，以确保符合优先级顺序。

3.1. 实现检查（空或满）

无论数组是有序还是无序，检查队列状态都涉及跟踪管理数组的指针或索引。

在数组中实现队列结构时，我们通常使用三个变量：

  • QUEUE_ARRAY：存储数据的一维数组。
  • Size：数组的最大容量。
  • Count（或 Front/Rear 等指针）：跟踪当前队列中的元素数量。

测试优先级队列是否为空

如果队列中存储的元素数量为零，则说明优先级队列为空。

实现检查（使用 Count 变量）：
IF Count == 0 THEN Queue_is_Empty

测试优先级队列是否已满

如果存储的元素数量等于数组的最大容量，则说明优先级队列已满。

实现检查（使用 Count 变量）：
IF Count == Size THEN Queue_is_Full

避免常见误区

不要把优先级队列和排序算法混为一谈！虽然向有序数组中插入元素（方案 2）看起来像排序，但该结构的主要任务是管理检索顺序，而不是永久性地整理数据集。我们只关心哪个元素是“下一个”被处理的。

4. 优先级队列的适用场景（应用）

当资源管理或顺序处理必须根据重要性而非时间先后进行时，优先级队列是必不可少的。

  • 操作系统调度：管理进程。关键系统进程（例如处理中断或错误）必须先于后台任务（例如磁盘碎片整理）执行，即使后台任务提交得更早。
  • 事件模拟：在模拟中，事件必须按其计划时间的先后顺序处理，此时时间本身就是优先级（时间越早，优先级越高）。
  • 带宽管理：网络数据包优先权。重要的数据包（如视频会议流量）应先于不太关键的数据（如大文件下载）发送。
  • 图论算法：优先级队列被用于实现某些关键的图论算法。
你知道吗？

最短路径算法——迪杰斯特拉算法 (Dijkstra’s algorithm)，很大程度上依赖于优先级队列来高效选择下一个要访问的节点。它始终优先考虑从起始点出发累计距离最短的节点，实际上就是将距离视为优先级！

学习要点

优先级队列根据分配的优先级值处理元素。虽然可以通过一维数组简单实现，但这通常需要在维护优先级顺序时不断进行元素的移动或搜索。它对于那些需要按重要性处理任务的系统来说至关重要。