JavaScript 优先队列

优先队列是一种特殊的队列，在这种数据结构中，元素的出队顺序取决于其优先级。优先队列通常用于调度问题、图形搜索算法等场景。

什么是优先队列？

优先队列是一种抽象数据类型，它类似于普通的队列或堆栈数据结构，但每个元素都有一个优先级关联。队列中的元素按照优先级顺序被服务。优先级高的元素先出队，优先级低的元素后出队。如果两个元素具有相同的优先级，则按照它们进入队列的顺序出队。

优先队列的应用

优先队列有多种实际应用，包括：

• 作业调度：操作系统使用优先队列来决定哪个进程应该首先获得CPU时间。
• 图搜索算法：如Dijkstra算法和A*搜索算法，使用优先队列来选择下一个需要处理的节点。
• 事件驱动模拟：在模拟系统中，优先队列可以用来存储事件，并按时间顺序处理这些事件。
• 网络路由：路由器使用优先队列来确定网络流量的传输顺序。

实现优先队列的数据结构

实现优先队列的一种常见方法是使用二叉堆。二叉堆是一种特殊的完全二叉树，它满足堆属性，即父节点的值总是大于或等于（最大堆）或小于或等于（最小堆）它的孩子节点的值。这使得我们可以轻松地获取最高优先级的元素（根节点），并维护队列的有序性。

最小优先队列

在最小优先队列中，优先级最高的元素是最小值。这意味着最小元素会首先出队。

最大优先队列

在最大优先队列中，优先级最高的元素是最大值。这意味着最大元素会首先出队。

优先队列的基本操作

优先队列支持以下基本操作：

• 插入（enqueue）：将一个新元素添加到优先队列中。
• 删除（dequeue）：移除并返回优先级最高的元素。
• 查看最高优先级元素（peek/look）：查看优先级最高的元素，但不移除它。
• 判断是否为空（isEmpty）：检查优先队列是否为空。
• 获取队列大小（size）：返回队列中的元素数量。

优先队列的实现

下面是使用JavaScript实现优先队列的示例代码，这里我们使用最小优先队列作为例子。

// www.javascriptcn.com code example
class PriorityQueue {
    constructor(comparator = (a, b) => a < b) {
        this._heap = [];
        this._comparator = comparator;
    }

    // 插入元素
    enqueue(value) {
        this._heap.push(value);
        this._siftUp();
    }

    // 移除并返回优先级最高的元素
    dequeue() {
        const poppedValue = this.peek();
        const bottom = this.size() - 1;

        if (bottom > 0) {
            this._swap(0, bottom);
        }

        this._heap.pop();

        if (this.size() > 0) {
            this._siftDown();
        }

        return poppedValue;
    }

    // 查看优先级最高的元素
    peek() {
        return this.size() === 0 ? null : this._heap[0];
    }

    // 判断队列是否为空
    isEmpty() {
        return this.size() === 0;
    }

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

    // 向上调整
    _siftUp() {
        let node = this.size() - 1;
        while (0 < node && this._shouldSiftUp(node)) {
            this._swap(node, this._parent(node));
            node = this._parent(node);
        }
    }

    // 向下调整
    _siftDown() {
        let node = 0;
        while (
            (node < this.size() && this._shouldSiftDown(node)) ||
            (this._left(node) < this.size() && this._shouldSwap(node, this._left(node))) ||
            (this._right(node) < this.size() && this._shouldSwap(node, this._right(node)))
        ) {
            let maxChild = (this._right(node) < this.size() && this._shouldSwap(node, this._right(node)))
                ? this._right(node)
                : this._left(node);

            this._swap(node, maxChild);
            node = maxChild;
        }
    }

    // 检查是否需要向上调整
    _shouldSiftUp(childIndex) {
        const parentIndex = this._parent(childIndex);
        return this._comparator(this._heap[childIndex], this._heap[parentIndex]);
    }

    // 检查是否需要向下调整
    _shouldSiftDown(parentIndex) {
        return (
            (this._left(parentIndex) < this.size() && this._shouldSwap(parentIndex, this._left(parentIndex))) ||
            (this._right(parentIndex) < this.size() && this._shouldSwap(parentIndex, this._right(parentIndex)))
        );
    }

    // 检查两个索引对应的元素是否需要交换
    _shouldSwap(parentIndex, childIndex) {
        return this._comparator(this._heap[childIndex], this._heap[parentIndex]);
    }

    // 交换两个元素的位置
    _swap(indexOne, indexTwo) {
        [this._heap[indexOne], this._heap[indexTwo]] = [this._heap[indexTwo], this._heap[indexOne]];
    }

    // 计算父节点的索引
    _parent(index) {
        return ((index + 1) >>> 1) - 1;
    }

    // 计算左子节点的索引
    _left(index) {
        return (index << 1) + 1;
    }

    // 计算右子节点的索引
    _right(index) {
        return (index + 1) << 1;
    }
}

示例用法

// www.javascriptcn.com code example
const priorityQueue = new PriorityQueue();

priorityQueue.enqueue(10);
priorityQueue.enqueue(5);
priorityQueue.enqueue(15);

console.log(priorityQueue.dequeue()); // 输出: 5
console.log(priorityQueue.dequeue()); // 输出: 10
console.log(priorityQueue.dequeue()); // 输出: 15

总结

通过本章的学习，您应该已经掌握了优先队列的基本概念、应用场景以及如何在JavaScript中实现优先队列。希望这些知识能够帮助您在实际项目中更有效地使用优先队列。