JavaScript 数组实现优先级队列的几种方法：含代码示例与性能对比

本文聚焦在 JavaScript 数组实现优先级队列的几种方法，并提供详细的 代码示例 与 性能对比要点。通过对比不同实现方式的时间复杂度和适用场景，读者可以根据实际需求选择最合适的方案。本篇内容紧密围绕“含代码示例与性能对比”的主题展开，便于在实际项目中快速落地。

1. 未排序数组的实现：插入后再排序

1.1 实现要点与代码示例

核心思想是将元素与优先级以对象形式存入一个数组，在取出时对整个数组按优先级进行排序，然后再弹出优先级最高（数值越小越优先）的项。插入操作是常量时间，但出队需要对整个数组排序，时间复杂度为 O(n log n)，对小数据量或出队远多于插入的场景可能还算合适。

// 未排序数组：出队时进行排序
class PriorityQueueUnsorted {constructor() {this.data = [];}enqueue(item, priority) {this.data.push({ item, priority });}dequeue() {if (this.data.length === 0) return null;this.data.sort((a, b) => a.priority - b.priority);return this.data.shift().item;}peek() {if (this.data.length === 0) return null;this.data.sort((a, b) => a.priority - b.priority);return this.data[0].item;}size() {return this.data.length;}
}

1.2 优缺点与适用场景

优点：实现简单、代码短，易于理解；适用于数据规模较小的情况，或者对出队性能要求不高的场景。
缺点：每次出队都要对整个数组排序，存在较高的时间成本；插入时也可能需要在后续操作中再次排序，因此整体吞吐量在大数据量场景下不理想。

2. 保持有序数组：二分查找插入的方法

2.1 实现要点与代码示例

核心在于将数组始终保持有序，通过二分查找确定插入位置，从而降低后续出队时的成本。插入的代价主要来自于数组的移动（shift），理论上时间复杂度为 O(n)；二分查找本身是 O(log n)，但移动成本仍然存在，因此总体上是 O(n) 的级别，但在大量读取场景中取出通常很快。

// 有序数组：使用二分查找插入保持有序
class PriorityQueueSorted {constructor() {this.data = [];}enqueue(item, priority) {const node = { item, priority };let left = 0;let right = this.data.length;// 二分查找插入位置while (left < right) {const mid = (left + right) >> 1;if (this.data[mid].priority <= priority) left = mid + 1;else right = mid;}this.data.splice(left, 0, node);}dequeue() {return this.data.shift()?.item ?? null;}peek() {return this.data[0]?.item ?? null;}size() {return this.data.length;}
}

2.2 优缺点与适用场景

优点：保持有序结构后，出队时直接访问首元素即可，读取效率高；插入时通过二分查找定位插入点，尽量减少比较次数。
缺点：尽管查找变快，但插入时仍需要在数组中移动元素，平均时间为 O(n)；对于高并发写入、大规模数据量，性能提升有限。

3. 基于堆（数组实现的最小堆）

3.1 实现要点与代码示例

最小堆是一种常用的优先级队列实现，使用数组来表示完全二叉树，插入后通过上浮（bubble up）保持堆序，出队则通过将末尾节点放到顶部再下沉（bubble down）来维持堆序。时间复杂度均为 O(log n)，且常数因子较小，适合高吞吐量场景。

// 基于数组实现的最小堆优先队列
class PriorityQueueHeap {constructor() {this.heap = [];}enqueue(item, priority) {const node = { item, priority };this.heap.push(node);this._bubbleUp(this.heap.length - 1);}dequeue() {if (this.heap.length === 0) return null;const top = this.heap[0];const end = this.heap.pop();if (this.heap.length > 0) {this.heap[0] = end;this._bubbleDown(0);}return top.item;}peek() {return this.heap[0]?.item ?? null;}size() {return this.heap.length;}_bubbleUp(index) {const node = this.heap[index];while (index > 0) {const parentIndex = (index - 1) >> 1;const parent = this.heap[parentIndex];if (parent.priority <= node.priority) break;this.heap[parentIndex] = node;this.heap[index] = parent;index = parentIndex;}}_bubbleDown(index) {const length = this.heap.length;const node = this.heap[index];while (true) {const left = index * 2 + 1;const right = left + 1;let smallest = index;if (left < length && this.heap[left].priority < this.heap[smallest].priority) smallest = left;if (right < length && this.heap[right].priority < this.heap[smallest].priority) smallest = right;if (smallest === index) break;this.heap[index] = this.heap[smallest];this.heap[smallest] = node;index = smallest;}}
}

3.2 优缺点与适用场景

优点：时间复杂度稳定在 O(log n)，在大量 insert/delete 场景下性能表现出色；内存使用规则且缓存友好，适合对吞吐量有严格要求的应用。
缺点：实现相对复杂，易出错；对于简单需求或小数据集，开销可能高于其他方法。

4. 基于桶的优先队列：桶化实现

4.1 实现要点与代码示例

桶化实现通过把优先级映射到离散的桶，同一桶内的元素按先进先出顺序处理，常用于优先级范围已知且离散的场景。插入通常是 O(1)，出队需要遍历桶以找到最小非空桶，复杂度依赖于最大优先级值。因此，它在优先级分布窄且范围有限时非常高效。

// 桶化实现：优先级为非负整数
class PriorityQueueBuckets {constructor(maxPriority = 1000) {this.buckets = Array.from({ length: maxPriority + 1 }, () => []);this.minIndex = 0;this.count = 0;}enqueue(item, priority) {if (priority < 0) throw new Error("priority must be non-negative");if (priority >= this.buckets.length) {const extra = priority - this.buckets.length + 1;this.buckets.push(...Array.from({ length: extra }, () => []));}this.buckets[priority].push(item);if (priority < this.minIndex) this.minIndex = priority;this.count++;}dequeue() {while (this.minIndex < this.buckets.length && this.buckets[this.minIndex].length === 0) this.minIndex++;if (this.minIndex >= this.buckets.length) return null;const item = this.buckets[this.minIndex].shift();this.count--;return item;}peek() {let idx = this.minIndex;while (idx < this.buckets.length && this.buckets[idx].length === 0) idx++;return idx < this.buckets.length ? this.buckets[idx][0] : null;}
}

4.2 优缺点与适用场景

优点：插入 O(1)，当优先级范围有限且离散时，整体性能非常优秀；实现简单、内存预测性好。
缺点：如果最大优先级值很大，桶数组需要大量内存；并且对非整数或大范围优先级不友好。

5. 多方法对比与综合要点

5.1 理论复杂度对比

在本文讨论的四种实现中，未排序数组的出队为 O(n log n)（因排序），保持有序数组的插入为 O(n)（因移动元素），堆实现的插入和删除均为 O(log n)，桶化实现的插入通常为 O(1)，但出队可能需要遍历若干桶。综合看，堆实现通常在高并发和大规模数据时表现最稳定，而桶化在优先级离散且范围受限时具有极高的吞吐率。

5.2 实际性能要点与适用建议

如果你的工作负载体现为“高频插入、高频出队且优先级分布较均匀”，堆实现（基于数组的二叉堆）往往是最佳折中，因为它提供稳定的 O(log n) 操作和低常数因子。
如果优先级为离散且范围明确，桶化实现在插入和局部排序方面会获得极高的性能优势，尤其是对大规模数据集。
若你的数据量较小、实现需要快速迭代，简单的未排序或保持有序数组的实现能够更快地完成开发与验证。

在实际项目中，可以基于以上四种方法做一个小型对比基准，例如对同一组任务进行多次 enqueue/dequeue，记录完成时间，再根据吞吐量、内存占用和实现复杂度选择最合适的实现。

最终，本文围绕的主题是：JavaScript 数组实现优先级队列的几种方法：含代码示例与性能对比，并通过多种实现方式展示了不同的权衡点，为你的前端或 Node.js 应用提供了可直接移植的方案。