优先队列（Priority Queue）

什么是优先队列？

优先队列（Priority Queue）是一种特殊的队列，其中每个元素都有一个“优先级”。出队时，总是移除优先级最高（或最低，取决于实现）的元素，而不是按照先进先出（FIFO）原则。

它广泛应用于任务调度、Dijkstra最短路径算法、Huffman编码、事件驱动模拟等场景。

核心特性

• 插入（enqueue）：添加一个带优先级的元素。
• 删除（dequeue）：移除并返回优先级最高的元素。
• 查看顶部（peek）：返回但不移除最高优先级元素。
• 通常基于堆（Heap）实现，以保证 O(log n) 的插入和删除效率。

JavaScript 简易实现

以下是一个基于最小堆的优先队列简易实现：

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  enqueue(val, priority) {
    this.heap.push({ val, priority });
    this.bubbleUp();
  }

  dequeue() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return top;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIdx = Math.floor((index - 1) / 2);
      if (this.heap[parentIdx].priority <= this.heap[index].priority) break;
      [this.heap[parentIdx], this.heap[index]] = [this.heap[index], this.heap[parentIdx]];
      index = parentIdx;
    }
  }

  bubbleDown() {
    let index = 0;
    const len = this.heap.length;
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;
      let smallest = index;

      if (left < len && this.heap[left].priority < this.heap[smallest].priority)
        smallest = left;
      if (right < len && this.heap[right].priority < this.heap[smallest].priority)
        smallest = right;

      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

交互演示

点击下方按钮查看优先队列入队/出队过程：

常见应用场景

1. 操作系统任务调度：高优先级任务先执行。
2. 图算法：如 Dijkstra 算法中选择当前最短路径节点。
3. 事件驱动模拟：按时间戳顺序处理事件。
4. 数据流中找 Top-K 元素：维护一个大小为 K 的优先队列。