⭐ 题目日期：

金山 - 2024/12/31

📝 题解：

优先队列（Priority Queue）是一种抽象数据结构，其核心特性是元素的出队顺序由优先级决定，而非传统队列的“先进先出”（FIFO）。以下是其关键要点：

---

1. 核心特性

• 元素带有优先级：每个元素关联一个优先级值（数值大小、自定义比较规则）。
• 按优先级出队：每次出队的元素是当前队列中优先级最高（或最低）的元素。
• 动态管理顺序：元素入队后，队列内部自动调整结构以维护优先级顺序。

---

2. 实现方式

优先队列通常基于**堆（Heap）**数据结构实现（如二叉堆），也可用平衡二叉搜索树（如红黑树）或有序数组实现，但堆的以下特性使其成为最优选择：

• 时间复杂度：
  • 插入元素（push）：O(log n)
  • 取出最高优先级元素（pop）：O(log n)
  • 查看最高优先级元素（peek/top）：O(1)
• 堆的类型：
  • 最大堆：根节点为最大值，用于获取优先级最高的元素。
  • 最小堆：根节点为最小值，用于获取优先级最低的元素。

---

3. 基本操作示例

以最大堆为例：

• 插入元素：将新元素添加到堆末尾，然后向上调整（heapify-up）以维护堆性质。
• 删除最高优先级元素：取出根节点，将末尾元素移到根位置，然后向下调整（heapify-down）。

---

4. 应用场景

优先队列广泛应用于需要动态管理优先级顺序的场景：

1. 任务调度：操作系统按任务优先级分配CPU资源。
2. 算法优化：
   • Dijkstra算法：优先处理距离最短的节点。
   • 哈夫曼编码：合并频率最小的节点。
   • A*寻路算法：选择预估路径代价最低的节点。
3. 实时系统：如医院急诊按病情严重程度分诊。
4. 合并K个有序链表：每次取最小元素。

---

5. 代码示例

不同语言中的优先队列实现：

Python（使用heapq模块，默认最小堆）

import heapq

# 创建最小堆（默认）
pq = []
heapq.heappush(pq, 3)  # 插入元素
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)

print(heapq.heappop(pq))  # 输出1（最小元素）

# 实现最大堆：插入时取负数
heapq.heappush(pq, -3)
heapq.heappush(pq, -1)
print(-heapq.heappop(pq))  # 输出3

Java（PriorityQueue类，默认最小堆）

import java.util.PriorityQueue;

// 默认最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(3);
minHeap.add(1);
minHeap.add(2);
System.out.println(minHeap.poll()); // 输出1

// 最大堆：通过Comparator反转顺序
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.add(3);
maxHeap.add(1);
System.out.println(maxHeap.poll()); // 输出3

C++（priority_queue，默认最大堆）

#include <queue>

// 默认最大堆
std::priority_queue<int> max_heap;
max_heap.push(3);
max_heap.push(1);
max_heap.push(2);
std::cout << max_heap.top(); // 输出3
max_heap.pop();

// 最小堆：使用greater比较器
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(3);
min_heap.push(1);
std::cout << min_heap.top(); // 输出1

---

6. 优先队列 vs 普通队列

特性	优先队列	普通队列
出队顺序	按优先级高低	先进先出（FIFO）
时间复杂度	插入/删除 O(log n)	插入/删除 O(1)（链表实现）
典型应用	任务调度、图算法优化	消息队列、缓冲区管理
实现结构	堆、平衡树	数组、链表

---

7. 常见问题

• 如何自定义优先级规则？
  通过实现比较器（Comparator）或重载运算符（如C++中的operator<）。

• 优先队列是否允许重复元素？
  是的，除非显式限制（如使用唯一性约束的堆）。

• 堆的数组表示如何计算父子节点？
  对于索引i：

  • 父节点：(i-1)/2
  • 左子节点：2i + 1
  • 右子节点：2i + 2

---

总结：优先队列通过高效维护元素的优先级顺序，成为解决动态排序问题的核心工具，其底层实现和灵活扩展性使其在算法和系统设计中广泛应用。