优先队列在JavaScript中的实现

优先队列（Priority Queue）是一种特殊的队列数据结构，其中每个元素都有一个关联的优先级。在执行操作时，优先级较高的元素会先于优先级较低的元素被处理。这种数据结构在各种应用中都非常有用，例如任务调度、事件循环、图形算法等。

在JavaScript中实现优先队列可以使用多种方法，包括数组、二叉堆或自定义的数据结构。本文将介绍如何使用二叉堆来实现优先队列，并提供一个简单的JavaScript实现示例。

二叉堆概述

二叉堆是一种完全二叉树，它满足以下性质：

1. 堆序性：对于任何节点i（除了根节点），其子节点的值总是小于（大顶堆）或大于（小顶堆）其父节点的值。
2. 完全性：除最后一层外，每一层都是完全填充的；最后一层的节点尽可能靠左排列。

二叉堆可以高效地实现插入和删除最小/最大元素的操作，时间复杂度分别为O(log n)和O(log n)，使得它成为实现优先队列的理想选择。

JavaScript实现优先队列

定义堆节点类

首先，我们需要定义一个堆节点类，包含节点值和其索引。

class HeapNode {
    constructor(value, index) {
        this.value = value;
        this.index = index;
    }
}

实现堆类

接下来，我们实现堆类，包括插入、删除最小元素、构建堆、以及获取堆的大小等基本操作。

class BinaryHeap {
    constructor(compareFn) {
        this.heap = [];
        this.compareFn = compareFn || (a, b) => a < b;
    }

    insert(value) {
        const node = new HeapNode(value, this.heap.length);
        this.heap.push(node);
        this.bubbleUp(this.heap.length - 1);
    }

    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.compareFn(this.heap[index], this.heap[parentIndex])) {
                [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    extractMin() {
        if (this.heap.length === 0) return null;
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return min.value;
    }

    bubbleDown(index) {
        const length = this.heap.length;
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let smallestIndex = index;

            if (leftChildIndex < length && this.compareFn(this.heap[leftChildIndex], this.heap[smallestIndex])) {
                smallestIndex = leftChildIndex;
            }

            if (rightChildIndex < length && this.compareFn(this.heap[rightChildIndex], this.heap[smallestIndex])) {
                smallestIndex = rightChildIndex;
            }

            if (smallestIndex !== index) {
                [this.heap[index], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[index]];
                index = smallestIndex;
            } else {
                break;
            }
        }
    }

    getSize() {
        return this.heap.length;
    }
}

使用示例

现在我们可以创建一个优先队列实例并进行操作：

const priorityQueue = new BinaryHeap((a, b) => a.priority - b.priority);

priorityQueue.insert({ value: 'Task A', priority: 2 });
priorityQueue.insert({ value: 'Task B', priority: 1 });
priorityQueue.insert({ value: 'Task C', priority: 3 });

console.log('Extracted:', priorityQueue.extractMin()); // 输出: Task B
console.log('Extracted:', priorityQueue.extractMin()); // 输出: Task A
console.log('Extracted:', priorityQueue.extractMin()); // 输出: Task C
console.log('Size:', priorityQueue.getSize()); // 输出: 0

这段代码展示了如何使用自定义的优先队列实现来管理任务的优先级顺序，确保了高优先级的任务优先被处理。

结论

通过上述实现，我们不仅理解了二叉堆的基本概念，还学习了如何在JavaScript中实现一个优先队列。这种方法适用于需要根据元素优先级进行高效排序和管理的应用场景。通过灵活调整比较函数，优先队列可以适应不同的需求，如任务调度、事件循环管理等。