JavaScript优先队列实现：二叉堆代码示例与复杂度分析

优先队列（Priority Queue）是一种特殊的队列，其中每个元素都有一个优先级。与普通队列不同，优先队列中的元素按照优先级顺序出队，而不是按照入队顺序。实现优先队列的常见方式包括使用二叉堆（Binary Heap）或平衡二叉搜索树（如AVL树、红黑树）。

下面是一个使用二叉堆（最小堆）实现优先队列的示例代码：

class PriorityQueue {
  constructor(comparator = (a, b) => a - b) {
    this.heap = [];
    this.comparator = comparator;
  }

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

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

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

  // 交换两个元素
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // 上浮操作
  bubbleUp(index) {
    while (index > 0 && this.comparator(this.heap[index], this.heap[this.parent(index)]) < 0) {
      this.swap(index, this.parent(index));
      index = this.parent(index);
    }
  }

  // 下沉操作
  bubbleDown(index) {
    let minIndex = index;
    const left = this.leftChild(index);
    const right = this.rightChild(index);

    if (left < this.heap.length && this.comparator(this.heap[left], this.heap[minIndex]) < 0) {
      minIndex = left;
    }

    if (right < this.heap.length && this.comparator(this.heap[right], this.heap[minIndex]) < 0) {
      minIndex = right;
    }

    if (index !== minIndex) {
      this.swap(index, minIndex);
      this.bubbleDown(minIndex);
    }
  }

  // 插入元素
  push(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  // 移除并返回优先级最高的元素
  pop() {
    if (this.isEmpty()) {
      return null;
    }
    const result = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return result;
  }

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

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

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

// 示例用法
const pq = new PriorityQueue();
pq.push(5);
pq.push(3);
pq.push(8);
pq.push(1);

console.log(pq.pop()); // 输出: 1
console.log(pq.pop()); // 输出: 3
console.log(pq.pop()); // 输出: 5
console.log(pq.pop()); // 输出: 8

代码说明：

1. 构造函数：PriorityQueue 类接受一个可选的比较函数 comparator，默认情况下使用 (a, b) => a - b，即最小堆。
2. 插入操作 (push)：将新元素插入到堆的末尾，然后通过 bubbleUp 操作将其上浮到正确的位置。
3. 移除操作 (pop)：移除并返回堆顶元素（优先级最高的元素），然后将堆的最后一个元素移动到堆顶，并通过 bubbleDown 操作将其下沉到正确的位置。
4. 查看操作 (peek)：返回堆顶元素，但不移除它。
5. 辅助方法：parent、leftChild、rightChild、swap 等方法用于操作堆结构。

复杂度分析：

• 插入操作 (push)：时间复杂度为 O(log n)，因为需要上浮操作。
• 移除操作 (pop)：时间复杂度为 O(log n)，因为需要下沉操作。
• 查看操作 (peek)：时间复杂度为 O(1)，因为直接访问堆顶元素。

应用场景：

优先队列常用于需要动态维护一组元素并快速获取最高优先级元素的场景，如任务调度、Dijkstra算法、Huffman编码等。

如果你有更复杂的需求，比如需要支持动态更新优先级，可以考虑使用更复杂的数据结构，如斐波那契堆。