优先队列是什么？JS实现全解析

优先队列是一种特殊的队列，它不遵循先进先出或后进先出的规则，而是根据元素的优先级进行处理。本文将深入探讨优先队列的概念，并通过JavaScript代码示例，详细讲解如何基于二叉堆实现高效的优先队列。重点介绍插入（enqueue）和取出最高优先级元素（dequeue）这两个核心操作，并分析其背后的“上浮”和“下沉”机制，确保堆结构的平衡。此外，还将对比优先队列与普通队列、栈的区别，以及它在操作系统任务调度、最短路径算法、AI寻路等实际开发场景中的应用。最后，对选择不同数据结构（如数组、链表、堆）实现优先队列的优劣势进行分析，助你选择最合适的方案。

优先队列按元素优先级处理而非入队顺序，核心操作为插入和取出，基于二叉堆实现高效，适用于任务调度、最短路径等需动态排序的场景。

优先队列并非传统意义上的“先进先出”或“后进先出”队列，它更像一个“按重要性排队”的系统。在这里，每个元素都携带一个优先级，系统会根据这个优先级来决定谁先被处理。优先级高的元素，无论何时进入队列，都将优先出队。你可以把它想象成医院的急诊室，病人不是按到达顺序看诊，而是病情最紧急的病人优先得到救治。

要用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

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。