优先队列按元素优先级处理而非入队顺序，核心操作为插入和取出，基于二叉堆实现高效，适用于任务调度、最短路径等需动态排序的场景。
优先队列并非传统意义上的“先进先出”或“后进先出”队列，它更像一个“按重要性排队”的系统。在这里，每个元素都携带一个优先级，系统会根据这个优先级来决定谁先被处理。优先级高的元素，无论何时进入队列，都将优先出队。你可以把它想象成医院的急诊室，病人不是按到达顺序看诊，而是病情最紧急的病人优先得到救治。
要用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 Dconsole.log('Next highest priority task:', pq.dequeue()); // 输出: Task Bconsole.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
以上就是什么是优先队列？JS如何实现优先队列的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1517527.html
微信扫一扫 
支付宝扫一扫 
