JavaScript 优先队列的实现

优先队列是一种特殊的队列，在这种队列中，元素被赋予优先级。当添加新元素时，它会根据其优先级被放置在适当的位置。优先队列通常支持以下操作：

• enqueue(item, priority): 添加一个具有特定优先级的新元素。
• dequeue(): 移除并返回具有最高优先级的元素。如果存在多个具有相同优先级的元素，则可以按任意顺序移除它们。
• peek(): 返回具有最高优先级的元素，但不移除它。
• isEmpty(): 检查优先队列是否为空。
• size(): 返回队列中的元素数量。

实现优先队列

使用数组实现优先队列

优先队列可以通过数组来实现，其中每个元素都是一个对象，包含了元素值和优先级。为了保持队列的排序，每次插入元素时都需要找到正确的位置插入。

// www.javascriptcn.com code example
class PriorityQueue {
    constructor() {
        this.items = [];
    }

    enqueue(element, priority) {
        let newItem = { element, priority };
        if (this.isEmpty()) {
            this.items.push(newItem);
        } else {
            let added = false;
            for (let i = 0; i < this.items.length; i++) {
                if (newItem.priority > this.items[i].priority) {
                    this.items.splice(i, 0, newItem);
                    added = true;
                    break;
                }
            }
            if (!added) {
                this.items.push(newItem);
            }
        }
    }

    dequeue() {
        if (this.isEmpty()) return "Underflow";
        return this.items.shift().element;
    }

    peek() {
        if (this.isEmpty()) return "No elements in Queue";
        return this.items[0].element;
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }

    printPQueue() {
        let str = "";
        for (let i = 0; i < this.items.length; i++)
            str += this.items[i].element + " ";
        return str;
    }
}

使用二叉堆实现优先队列

使用二叉堆（通常是最大堆或最小堆）可以更高效地实现优先队列。这种方法的时间复杂度更低，更适合处理大量数据的情况。

最大堆实现

最大堆是一种完全二叉树，其中每个父节点的值都大于或等于其子节点的值。这种特性使得根节点总是具有最大值，非常适合用来实现优先队列。

// www.javascriptcn.com code example
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    // 获取父节点索引
    getParentIndex(i) {
        return Math.floor((i - 1) / 2);
    }

    // 获取左子节点索引
    getLeftChildIndex(i) {
        return 2 * i + 1;
    }

    // 获取右子节点索引
    getRightChildIndex(i) {
        return 2 * i + 2;
    }

    // 交换两个节点的值
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

    // 插入新元素
    insert(value) {
        this.heap.push(value);
        let index = this.heap.length - 1;
        let parent = this.getParentIndex(index);

        while (index !== 0 && this.heap[parent] < this.heap[index]) {
            this.swap(parent, index);
            index = parent;
            parent = this.getParentIndex(index);
        }
    }

    // 获取最大值
    getMax() {
        return this.heap[0];
    }

    // 删除最大值
    extractMax() {
        const max = this.getMax();
        this.heap[0] = this.heap.pop();

        let index = 0;
        let leftChild, rightChild;

        while (true) {
            leftChild = this.getLeftChildIndex(index);
            rightChild = this.getRightChildIndex(index);

            if (leftChild >= this.heap.length && rightChild >= this.heap.length) break;

            let maxChild = leftChild;
            if (rightChild < this.heap.length && this.heap[rightChild] > this.heap[leftChild]) {
                maxChild = rightChild;
            }

            if (this.heap[index] >= this.heap[maxChild]) break;

            this.swap(index, maxChild);
            index = maxChild;
        }

        return max;
    }

    // 判断是否为空
    isEmpty() {
        return this.heap.length === 0;
    }

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

// 使用最大堆实现优先队列
class PriorityQueueUsingHeap {
    constructor() {
        this.maxHeap = new MaxHeap();
    }

    enqueue(value) {
        this.maxHeap.insert(value);
    }

    dequeue() {
        return this.maxHeap.extractMax();
    }

    peek() {
        return this.maxHeap.getMax();
    }

    isEmpty() {
        return this.maxHeap.isEmpty();
    }

    size() {
        return this.maxHeap.size();
    }
}

以上是使用数组和二叉堆实现优先队列的基本方法。实际应用中可以根据具体需求选择合适的数据结构和算法来优化性能。