优先队列
🧑💻 作者: 一可爱小白兔
📦 版本: 1.0.0
📄 字数(字): 0
⏳ 时长(min): 0
📅 发表于: 2025-04-18
⏱️ 更新于: 2026-02-03
笔记
优先队列（Priority Queue）是一种特殊的队列数据结构，其中每个元素都有一个优先级，出队时总是移除优先级最高的元素。
基本特性
- 插入（enqueue / push）：向队列中添加一个带有优先级的元素。
- 删除（dequeue / pop）：移除并返回当前优先级最高的元素。
- 查看顶部（peek / top）：返回但不移除优先级最高的元素。
常见实现方式
| 实现方式 | 插入时间复杂度 | 删除时间复杂度 | 说明 |
|---|---|---|---|
| 无序数组/链表 | O(1) | O(n) | 插入快，删除慢 |
| 有序数组/链表 | O(n) | O(1) | 删除快，插入慢 |
| 二叉堆（Binary Heap） | O(log n) | O(log n) | 最常用，平衡效率 |
二叉堆简介（用于实现优先队列）
- 最大堆（Max-Heap）：父节点 ≥ 子节点 → 根为最大值。
- 最小堆（Min-Heap）：父节点 ≤ 子节点 → 根为最小值。
- 完全二叉树，通常用 数组存储：
- 父节点索引
i的左孩子：2 * i + 1 - 右孩子：
2 * i + 2 - 孩子节点的父节点：
(i - 1) / 2
- 父节点索引
堆操作：
- 上浮（swim）：插入后调整。
- 下沉（sink）：删除根后调整。
典型应用场景
- 任务调度：高优先级任务先执行。
- Dijkstra 最短路径算法：每次取出距离最小的未访问节点。
- Huffman 编码：构建最优前缀编码树。
- Top-K 问题：如找最大的 K 个数（用最小堆维护 K 个元素）。
- 事件驱动模拟：按时间戳优先处理事件。