优先队列 (Priority Queue)

1. 算法说明

传统队列是先进先出 (FIFO). 在实现上, 使用线性表即可实现. 在 JavaScript 语言中, 使用数组, 并借助 push(), shift() 或 unshift(), pop() 方法就可以很容易的实现出.

但是优先队列, 数据进入不做要求, 但数据取出, 是按照数据的权值 (最大权值, 或最小权值) 进行取出的.

通常, 优先队列结构中, 权值相同的数据, 不一定保证 FIFO.

换句话说, 优先队列的核心是需要提供一个数据结构:

该数据结构可以尽可能快速的查询优先级最高/最低的数据.
数据存入的时候, 会按照该数据结构存储 (并非数组那样简单的线性存储).

其矛盾点在于:

如果存储数据的时候, 如同数组那样简单存储, 存储时效率会很高, 性能很好.
由于存入的数据具有随机性, 取出数据时, 需要对数据进行全部检索, 来找寻权值最高或最低的数据进行取出.

平衡这两个性能, 做到性能可接受是优先队列的重点.

有一个医院排队的例子(急诊分诊系统): 病人排队时按照普通队列开始的, 但是医生的救治需要按照病情的急缓来进行.

2. 简单的理解

使用 js 的理解优先队列.

const queue = []
/** 插入元素, 最简单的插入方法 */
function insert(n) {
    queue.push(n)
}
/** 取出优先级最高的数据, 也是权值最大的数据 */
function extract_max() {
    const _max = findWeightMax(queue) // 简单优先级最高的节点, 具体怎么检索, 需要特性的数据结构.
    const _i = queue.indexOf(_max)    // 找到目标数据后, 取出,需要从原集合中移除该数据.
    queue.splice(_i, 1)
    return _max
}

这里仅仅为了理解优先队列的逻辑含义, 使用最简单的方法来模拟.

3. 可行性方案

通常实现优先队列使用堆数据结构.

实现方式	插入时间	提取最值时间	是否推荐
二叉堆(推荐)	$O (\log n)$	$O (\log n)$	强烈推荐.
斐波那契堆	$O (1)$	$O (\log n)$	复杂, 特定场景使用.
有序数组	$O (\log n)$	$O (1)$	插入太慢, 不推荐.
无序数组	$O (1)$	$O (\log n)$	查找最值太慢, 不推荐.
平衡二叉搜索树	$O (l o g n)$	$O (\log n)$	可用, 但比堆复杂.

实现该数据结构通常需要提供:

操作	说明
`insert(element, priority)`	插入元素, 并制定其优先级.
`extract_max()` 或 `extract_min()`	取出并删除优先级最高(低)的元素.
`peek()` / `top()`	查看最高优先级的元素 (不会删除元素).
`isEmpty()`	判断是否为空.

具体实现方案, 暂略 (2025年9月10日11:57:54)

C# 中使用 .NET Core, 有 PriorityQueue 数据类型, 实现了优先队列, 早期的 Fx 中没有该实现.
JavaScript 中可以使用 heap-js 包来实现.