JS实现优先级队列的几种方法

## JS数组实现优先级队列方法：高效管理任务与数据 在JavaScript开发中，优先级队列是一种强大的数据结构，用于管理需要按重要性排序的任务或数据。本文深入探讨了如何利用JS数组模拟堆（Heap）的特性，实现高效的优先级队列。相较于其他数据结构，数组在内存连续性和索引计算方面具有优势，能提升缓存命中率并简化操作。本文提供了一个完整的`PriorityQueue`类实现，包括enqueue、dequeue、peek等关键方法，并详细解释了如何通过自定义比较器处理不同优先级元素，以及如何引入序列号确保相同优先级元素的顺序稳定性。此外，文章还探讨了优先级队列在任务调度、图算法、事件模拟等实际应用场景中的应用，帮助开发者更好地理解和运用这一重要的数据结构。

使用数组实现优先级队列的核心原因是其内存连续性和索引计算的直观性，能通过数学公式直接定位父子节点，提升缓存命中率并简化操作；2. 优先级队列常见于任务调度、图算法（如Dijkstra和Prim）、事件模拟、霍夫曼编码和网络数据包处理等需按重要性排序的场景；3. 处理相同优先级元素时，标准堆不保证顺序稳定性，若需稳定应引入序列号作为次要比较依据，在比较器中优先级相同时按插入顺序排序，从而实现稳定出队。

JavaScript数组实现优先级队列，核心在于模拟堆（Heap）的数据结构特性，通过巧妙地管理数组元素的插入和删除，确保优先级最高的元素总能被快速访问。这就像我们把一个无序的列表，用一套规则整理成了一个半有序的树形结构，只不过这个“树”是扁平化地存储在数组里的。

解决方案

class PriorityQueue {
    constructor(comparator = (a, b) => a[0] - b[0]) { // 默认比较器：基于元素的第一个值（优先级）
        this.heap = [];
        this.comparator = comparator; // 允许自定义比较函数
    }

    // 获取队列大小
    size() {
        return this.heap.length;
    }

    // 检查队列是否为空
    isEmpty() {
        return this.heap.length === 0;
    }

    // 查看优先级最高的元素（不移除）
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.heap[0];
    }

    // 插入元素
    enqueue(element) {
        this.heap.push(element);
        this._bubbleUp(); // 元素上浮以维护堆的性质
    }

    // 移除并返回优先级最高的元素
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const min = this.heap[0];
        const last = this.heap.pop();
        if (!this.isEmpty()) {
            this.heap[0] = last;
            this._sinkDown(); // 元素下沉以维护堆的性质
        }
        return min;
    }

    // 内部方法：元素上浮
    _bubbleUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            // 如果当前元素优先级高于父元素，则交换
            if (this.comparator(this.heap[index], this.heap[parentIndex]) < 0) {
                [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
                index = parentIndex;
            } else {
                break; // 堆性质已满足
            }
        }
    }

    // 内部方法：元素下沉
    _sinkDown() {
        let index = 0;
        const length = this.heap.length;
        const element = this.heap[0];

        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let swap = null; // 记录需要交换的子节点索引

            // 检查左子节点
            if (leftChildIndex < length) {
                if (this.comparator(this.heap[leftChildIndex], element) < 0) {
                    swap = leftChildIndex;
                }
            }

            // 检查右子节点
            if (rightChildIndex < length) {
                // 如果右子节点存在，且优先级比当前元素高
                // 并且（如果左子节点存在且优先级比右子节点低）或者（左子节点不存在）
                if (this.comparator(this.heap[rightChildIndex], element) < 0 &&
                    (swap === null || this.comparator(this.heap[rightChildIndex], this.heap[leftChildIndex]) < 0)) {
                    swap = rightChildIndex;
                }
            }

            if (swap === null) {
                break; // 没有更小的子节点，堆性质已满足
            }

            [this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
            index = swap;
        }
    }
}

// 示例用法：
// 创建一个最小优先级队列，元素可以是 [优先级, 值]
// const pq = new PriorityQueue();
// pq.enqueue([3, '任务C']);
// pq.enqueue([1, '任务A']);
// pq.enqueue([2, '任务B']);
// console.log(pq.dequeue()); // 输出 [1, '任务A']
// console.log(pq.peek());    // 输出 [2, '任务B']

// 创建一个最大优先级队列（通过修改比较器）
// const maxPQ = new PriorityQueue((a, b) => b[0] - a[0]);
// maxPQ.enqueue([3, '高优先级']);
// maxPQ.enqueue([1, '低优先级']);
// maxPQ.enqueue([2, '中优先级']);
// console.log(maxPQ.dequeue()); // 输出 [3, '高优先级']

为什么选择数组实现优先级队列，而不是其他数据结构？

说实话，用数组来实现优先级队列，也就是我们常说的“堆”，这是一种非常经典且高效的选择。它不像链表那样需要额外的指针开销，也不像红黑树那样在实现上复杂得让人头疼。数组的优点在于它的内存连续性和索引计算的直观性。

首先，内存连续性意味着更好的缓存局部性。当数据在内存中是连续存放的时候，CPU在读取一个元素时，很可能会把周围的元素也一并预读到缓存里，这对于频繁访问数据的情况来说，能显著提升性能。想象一下，如果你在书架上找书，书都挨着放，总比你每次都要跑去不同的房间找书要快得多。

其次，索引计算的直观性是数组作为堆底层结构的杀手锏。在一个完全二叉树中，一个节点的父节点、左右子节点的位置，都可以通过简单的数学公式从当前节点的索引推算出来。比如，对于索引i的节点：

• 它的父节点是 Math.floor((i - 1) / 2)
• 它的左子节点是 2 * i + 1
• 它的右子节点是 2 * i + 2 这种直接的映射关系，省去了维护复杂指针的麻烦，让插入（上浮）和删除（下沉）操作变得高效且易于理解。虽然在JavaScript这种高级语言里，我们不太需要直接关心内存分配，但这种基于数组的结构，其内在的逻辑美和性能优势依然是显而易见的。相比之下，如果用链表来构建堆，每次查找父子节点都需要遍历，效率会大打折扣。而平衡二叉搜索树（如AVL树、红黑树）虽然也能实现优先级队列，但其实现复杂度和维护成本远高于堆，对于仅仅需要“快速获取最大/最小元素”的场景来说，堆的O(log N)时间复杂度已足够优秀，且常数因子更小。

优先级队列在实际开发中有哪些常见的应用场景？

优先级队列这东西，在计算机科学里简直是无处不在，它解决的核心问题就是“谁先来，谁有更高权限”。在实际开发中，我个人觉得它用得最多的地方，大概就是那些需要调度和优化的场景。

一个很典型的例子是任务调度。比如操作系统里的进程调度，哪个进程CPU使用率高，哪个I/O密集型，它们可能需要不同的优先级。优先级队列就能确保高优先级的任务能先获得CPU时间片。游戏开发里也常用，比如AI寻路，或者粒子效果的渲染顺序，都可以用优先级队列来管理，确保关键的计算或视觉效果优先处理。

再比如图算法。著名的Dijkstra最短路径算法，或者Prim最小生成树算法，它们的核心逻辑都依赖于一个优先级队列来高效地选择下一个要访问的节点。每次都从队列中取出当前距离最短或权重最小的边，这正是优先级队列的拿手好戏。

还有一些不那么显眼但同样重要的应用，像事件模拟。在离散事件模拟系统中，所有待发生的事件都会被放入一个优先级队列，按照事件发生的时间点作为优先级排序，这样系统就能按时间顺序精确地处理事件。又比如数据压缩里的霍夫曼编码，构建霍夫曼树的过程就需要一个优先级队列来不断合并频率最低的两个节点。

甚至在一些网络数据包处理中，为了保证某些关键数据包（比如实时语音、视频流）的传输质量，也会用到优先级队列，确保它们能优先被发送。可以说，任何需要“按重要性顺序处理”的场景，优先级队列都是一个非常自然且高效的解决方案。

在实现过程中，如何处理相同优先级的元素？

处理相同优先级的元素，这确实是个很有意思的问题，也是实现一个健壮优先级队列时需要考虑的细节。我的经验是，标准的二叉堆（无论是最小堆还是最大堆）实现，通常并不保证相同优先级元素的相对顺序。这意味着，如果你插入了两个优先级都是5的元素A和B，你无法预知是A先被取出，还是B先被取出。这取决于它们在堆结构中的具体位置，以及在_bubbleUp或_sinkDown过程中遇到的比较路径。

在很多场景下，这种不确定性是完全可以接受的。比如，你只是想找出当前最紧急的那个任务，至于有多个同样紧急的任务，哪个先执行都行。

但如果你的业务逻辑对相同优先级元素的稳定性有要求，也就是说，它们必须按照它们被插入时的顺序（先进先出）被取出，那么你就需要对优先级队列的实现做一些小小的修改。

一个常见的策略是引入一个“时间戳”或“序列号”作为次要优先级。当你插入一个元素时，除了它的主优先级，再给它附带一个递增的序列号。这样，当两个元素的主优先级相同时，你的比较器就会去比较它们的序列号，序列号小的（即插入时间更早的）优先级更高。

举个例子，你的元素不再是 [优先级, 值]，而是 [优先级, 序列号, 值]。 你的比较器就需要这样调整：

class PriorityQueue {
    constructor(comparator = (a, b) => {
        // 优先比较主优先级
        if (a[0] !== b[0]) {
            return a[0] - b[0];
        }
        // 主优先级相同，比较序列号（次要优先级），确保稳定性
        return a[1] - b[1]; 
    }) {
        this.heap = [];
        this.comparator = comparator;
        this.insertionCount = 0; // 用于生成唯一的序列号
    }

    enqueue(element) {
        // 插入时附带序列号
        this.heap.push([element[0], this.insertionCount++, element[1]]); 
        this._bubbleUp();
    }

    // dequeue, peek 等方法需要注意返回的元素结构是 [优先级, 序列号, 值]
    // 外部使用时可能需要解构或只取值部分
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const minWithSerial = this.heap[0];
        const last = this.heap.pop();
        if (!this.isEmpty()) {
            this.heap[0] = last;
            this._sinkDown();
        }
        // 返回原始值，或者带序列号的完整元素
        return minWithSerial; 
    }
    // ... 其他方法保持不变
}

// 示例：
// const stablePQ = new PriorityQueue();
// stablePQ.enqueue([5, '任务A']); // 内部存储为 [5, 0, '任务A']
// stablePQ.enqueue([5, '任务B']); // 内部存储为 [5, 1, '任务B']
// stablePQ.enqueue([3, '任务C']); // 内部存储为 [3, 2, '任务C']
// console.log(stablePQ.dequeue()); // 输出 [3, 2, '任务C']
// console.log(stablePQ.dequeue()); // 输出 [5, 0, '任务A'] (因为序列号0比1小)
// console.log(stablePQ.dequeue()); // 输出 [5, 1, '任务B']

这种做法虽然会增加一点点存储开销，但对于需要稳定性的场景来说，是值得的。如果你的应用对性能要求极致，并且确定不需要稳定性，那么保持默认的不稳定行为会更简单高效。选择哪种方式，最终还是取决于具体的业务需求。

本篇关于《JS实现优先级队列的几种方法》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！