优先队列按元素优先级处理而非入队顺序，核心操作为插入和取出，基于二叉堆实现高效，适用于任务调度、最短路径等需动态排序的场景。
优先队列并非传统意义上的“先进先出”或“后进先出”队列，它更像一个“按重要性排队”的系统。在这里，每个元素都携带一个优先级，系统会根据这个优先级来决定谁先被处理。优先级高的元素，无论何时进入队列，都将优先出队。你可以把它想象成医院的急诊室，病人不是按到达顺序看诊，而是病情最紧急的病人优先得到救治。
要用JavaScript实现一个优先队列，最常见且高效的方式是基于二叉堆（Binary Heap）。通常，我们用一个数组来模拟堆的结构。这里我们以最小堆（Min-Heap）为例，即优先级最低（数值最小）的元素优先出队。
核心操作无非就是两点：插入（
enqueue或
insert）和取出最高优先级元素（
dequeue或
extractMin）。
插入操作 (enqueue): 新元素总是先加到数组的末尾，然后通过“上浮”（
bubbleUp或
heapifyUp）操作，将其与父节点比较并交换，直到它找到合适的位置，即比父节点大但比子节点小（对于最小堆）。
取出最高优先级元素 (dequeue): 最高优先级元素（最小堆的根节点）总是在数组的第一个位置。取出它之后，我们需要将数组的最后一个元素移到顶部，然后通过“下沉”（
sinkDown或
heapifyDown）操作，将其与子节点比较并交换，直到它找到合适的位置，重新维护堆的性质。
class PriorityQueue {
constructor() {
this.heap = []; // 存储堆元素的数组
}
// 辅助函数：获取父节点索引
_getParentIndex(i) {
return Math.floor((i - 1) / 2);
}
// 辅助函数：获取左子节点索引
_getLeftChildIndex(i) {
return 2 * i + 1;
}
// 辅助函数：获取右子节点索引
_getRightChildIndex(i) {
return 2 * i + 2;
}
// 辅助函数：交换元素
_swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
// 插入元素
enqueue(element, priority) {
const node = { element, priority };
this.heap.push(node); // 添加到数组末尾
this._bubbleUp(); // 执行上浮操作
}
_bubbleUp() {
let index = this.heap.length - 1; // 新元素的当前索引
while (index > 0) {
let parentIndex = this._getParentIndex(index);
// 如果当前元素的优先级比父节点高（数值小），则交换
if (this.heap[index].priority < this.heap[parentIndex].priority) {
this._swap(index, parentIndex);
index = parentIndex; // 更新索引到父节点位置，继续向上比较
} else {
break; // 已经找到正确位置，无需再上浮
}
}
}
// 取出最高优先级元素（最小元素）
dequeue() {
if (this.isEmpty()) {
return null;
}
if (this.heap.length === 1) {
return this.heap.pop().element; // 只有一个元素直接取出
}
const min = this.heap[0]; // 堆顶元素是优先级最高的
this.heap[0] = this.heap.pop(); // 将最后一个元素移到顶部
this._sinkDown(); // 通过下沉操作重新维护堆的性质
return min.element;
}
_sinkDown() {
let index = 0; // 从堆顶开始下沉
const length = this.heap.length;
const element = this.heap[0]; // 当前要下沉的元素
while (true) {
let leftChildIndex = this._getLeftChildIndex(index);
let rightChildIndex = this._getRightChildIndex(index);
let swapIndex = null; // 记录需要交换的子节点索引
// 检查左子节点是否存在且优先级更高
if (leftChildIndex < length) {
if (this.heap[leftChildIndex].priority < element.priority) {
swapIndex = leftChildIndex;
}
}
// 检查右子节点是否存在，并与当前最小的（或左子节点）比较
if (rightChildIndex < length) {
if (
(swapIndex === null && this.heap[rightChildIndex].priority < element.priority) || // 如果左子节点没有更小，检查右子节点
(swapIndex !== null && this.heap[rightChildIndex].priority < this.heap[leftChildIndex].priority) // 如果左子节点更小，再比较右子节点和左子节点谁更小
) {
swapIndex = rightChildIndex;
}
}
if (swapIndex === null) {
break; // 已经找到正确位置，无需再下沉
}
this._swap(index, swapIndex); // 交换
index = swapIndex; // 更新索引，继续向下
}
}
isEmpty() {
return this.heap.length === 0;
}
peek() {
if (this.isEmpty()) {
return null;
}
return this.heap[0].element; // 查看堆顶元素
}
size() {
return this.heap.length;
}
}
// 示例用法
const pq = new PriorityQueue();
pq.enqueue('Task A', 3);
pq.enqueue('Task B', 1);
pq.enqueue('Task C', 2);
pq.enqueue('Task D', 0);
console.log('Highest priority task:', pq.dequeue()); // 输出: Task D
console.log('Next highest priority task:', pq.dequeue()); // 输出: Task B
console.log('Queue size:', pq.size()); // 输出: 2
### 优先队列与普通队列、栈有何不同？
你可能觉得队列和栈这些数据结构已经够用了，为什么还要一个“优先队列”呢？它们的核心区别在于元素的出队顺序。
普通队列（FIFO - First In, First Out）就像排队买票，先到先得，不看你身份多尊贵。栈（LIFO - Last In, First Out）则像一摞盘子，最后放上去的总是第一个被拿走。它们都严格遵循一个固定的顺序规则。
优先队列则打破了这种僵化的顺序。它不看你什么时候来，只看你“有多重要”。它的出队顺序完全取决于元素的优先级，优先级高的，即便你刚进来，也可能插队到最前面。这种灵活的“插队”机制，让它在很多需要动态调整处理顺序的场景下显得尤为重要。你可以把优先级想象成一个数字，数字越小（或越大，取决于实现），优先级越高。这种基于优先级的动态排序，是它与普通队列和栈最根本的区别。
### 优先队列在实际开发中有哪些常见应用场景？
优先队列这东西，听起来有点抽象，但实际上它在软件世界里无处不在，解决了很多看似复杂的问题。
比如说，**操作系统的任务调度**。CPU资源有限，不可能同时处理所有任务。哪些任务应该优先执行？是用户交互的实时任务，还是后台的批量处理？这里就需要一个优先队列来根据任务的优先级（比如I/O密集型、计算密集型、用户优先级等）来决定下一个被执行的任务。
再比如，**网络路由中的最短路径算法**，像Dijkstra算法。它在寻找从起点到所有其他节点的最短路径时，会不断从一个优先队列中取出当前“距离最小”的节点进行扩展。每次都优先处理距离最短的，这不就是典型的优先队列应用吗？
游戏开发里也有它的身影，比如**AI寻路**（A*算法）。A*算法在探索地图时，会把待探索的节点放入一个优先队列，优先级基于预估的总成本（已走距离 + 预计到目标距离）。这样就能优先探索那些看起来更有希望通向目标的路径。
还有一些**事件模拟**、**数据压缩（如Huffman编码）**、甚至你平时用的**消息队列**，在需要保证某些消息优先被处理时，其底层也可能用到优先队列的思想。可以说，任何你需要“按重要性”来处理一堆事物的场景，优先队列都可能是一个优雅的解决方案。
### 实现优先队列时，选择不同数据结构（如数组、链表、堆）的优劣势分析
我们上面用了堆来实现优先队列，但它不是唯一选项。理论上，数组、链表也能实现，只不过效率上会有很大差异。理解这些差异，能帮助你在实际项目中做出更明智的选择。
**1. 基于无序数组或链表：**
* **实现方式：** 最简单粗暴的方法。插入时直接加到末尾。取出优先级最高的元素时，需要遍历整个数组或链表，找到优先级最高的那个。
* **优势：** 实现起来极其简单，代码量少。
* **劣势：** 效率极低。插入操作是O(1)，但取出最高优先级元素（`dequeue`）和查找（`peek`）操作都需要O(n)的时间复杂度，因为每次都要遍历。这在数据量稍大时是不可接受的。想象一下，每次急诊室要找最紧急的病人，都要把所有病人问一遍，这效率简直了。
**2. 基于有序数组或链表：**
* **实现方式：** 始终保持数组或链表有序。插入新元素时，需要找到它合适的位置并插入，以维持顺序。
* **优势：** 取出最高优先级元素（`dequeue`）和查找（`peek`）操作可以达到O 
