优先队列

基本概念

优先队列（Priority Queue）：是一种为每个元素分配优先级的特殊队列结构。每次访问或移除元素时，总是优先处理优先级最高的元素。
优先队列与普通队列的核心区别在于 出队顺序：

• 普通队列按照「先进先出（First In, First Out）」原则，元素按入队顺序依次出队。
• 优先队列则根据元素的优先级决定出队顺序，优先级高的元素先出队，优先级低的元素后出队，遵循 「优先级高者先出」 的规则，与入队顺序无关。

内部实现：

优先队列的基本操作与普通队列类似，主要包括 「入队」 和 「出队」，但在出队时会优先移除优先级最高的元素。
优先队列的实现方式主要有三种：数组（顺序存储）、链表（链式存储） 和 二叉堆结构。其中，最常用且高效的是基于二叉堆的实现。下面简要对比三种方案：

• 数组（顺序存储）：入队时直接将元素插入数组末尾，时间复杂度为 O(1)；出队时需遍历整个数组以找到优先级最高的元素并删除，时间复杂度为 O(n)。
• 链表（链式存储）：链表内元素按优先级有序排列，入队时需找到合适插入位置，时间复杂度为 O(n)；出队时直接移除链表头节点，时间复杂度为 O(1)。
• 二叉堆结构：通过二叉堆维护优先级顺序，入队操作（插入新元素）和出队操作（弹出优先级最高元素）均为 O(log⁡n)，效率较高。

三种实现方式的时间复杂度对比如下：

实现方式	入队操作	出队操作（取优先级最高元素）
二叉堆	$O(log⁡n)$	$O(log⁡n)$
数组	$O(1)$	$O(n)$
链表	$O(n)$	$O(1)$

应用场景：

优先队列在实际开发和算法设计中有着广泛的应用，常见场景包括：

• 数据压缩：如赫夫曼编码算法中，频率最低的节点优先合并。
• 最短路径搜索：如 Dijkstra 算法，优先扩展当前距离最小的节点。
• 最小生成树构建：如 Prim 算法，优先选择权值最小的边。
• 任务调度：根据任务优先级动态分配执行顺序。
• 事件驱动仿真：如排队系统，优先处理最早到达或优先级最高的事件。
• Top-K 问题：如查找第 k 大（小）元素、实时维护前 K 个高频元素等。