参考链接：https://github.com/itcharge/LeetCode-Py
一、简介
优先队列（Priority Queue）：一种特殊的队列。在优先队列中，元素被赋予优先级，当访问队列元素时，具有最高优先级的元素最先删除。
优先队列与普通队列最大的不同点在于出队顺序。
- 普通队列的出队顺序跟入队顺序相关，符合「先进先出（First in, First out）」的规则。
- 而优先队列的出队顺序跟入队顺序无关，优先队列是按照元素的优先级来决定出队顺序的。优先级高的元素优先出队，优先级低的元素后出队。优先队列符合 「最高级先出（First in, Largest out）」 的规则。
二、适用场景
- 数据压缩：赫夫曼编码算法；
- 最短路径算法：Dijkstra 算法；
- 最小生成树算法：Prim 算法；
- 任务调度器：根据优先级执行系统任务；
- 事件驱动仿真：顾客排队算法；
- 选择问题：查找第 k 个最小元素。
- Python 中也可以通过 heapq 来实现优先队列。
三、实现方式
优先队列所涉及的基本操作跟普通队列差不多，主要是 「入队操作」 和 「出队操作」。
而优先队列的实现方式也有很多种，除了使用「数组（顺序存储）实现」与「链表（链式存储）实现」之外，我们最常用的是使用 「二叉堆结构实现」优先队列。
以下是三种方案的介绍和总结。
- 数组（顺序存储）实现优先队列：入队操作直接插入到数组队尾，时间复杂度为
。出队操作需要遍历整个数组，找到优先级最高的元素，返回并删除该元素，时间复杂度为
。
- 链表（链式存储）实现优先队列：链表中的元素按照优先级排序，入队操作需要为待插入元素创建节点，并在链表中找到合适的插入位置，时间复杂度为
- 二叉堆结构实现优先队列：构建一个二叉堆结构，二叉堆按照优先级进行排序。入队操作就是将元素插入到二叉堆中合适位置，时间复杂度为
。吹对操作则返回二叉堆中优先级最大节点并删除，时间复杂度也是
三种结构实现的优先队列入队操作和出队操作的时间复杂度总结如下：
时间复杂度对比图
四、总结
经过为期半个月的力扣刷题学习，我从害怕做题到有一点点兴趣，我觉得这件事情是值得继续坚持下去的，虽然现在还是不太懂，至少在旁边转悠，继续前进应该能到门边上的。这次课程的设计者非常用心，知识点很细致，而且很全面，可能有一点点小的误差被其他同学发现了，但这是一件更好的事情，不断地改进将会得到更进一步的提升。
