优先队列：原理、实现与应用场景 | 数据结构指南

优先队列（Priority Queue）是一种抽象数据类型，它类似于常规的队列或栈，但每个元素都有一个“优先级”。在优先队列中，元素被赋予优先级，优先级最高的元素最先被移除。优先队列通常用于任务调度、图算法（如Dijkstra算法）、数据压缩（如Huffman编码）等场景。

优先队列的特性

1. 插入（Enqueue）：将元素插入队列，并根据其优先级放置在适当的位置。
2. 删除（Dequeue）：移除并返回优先级最高的元素。
3. 查看（Peek）：返回优先级最高的元素，但不移除它。

实现方式

优先队列可以通过多种数据结构来实现，常见的有：

1. 数组或链表：

   • 插入操作：O(1) 或 O(n)（如果需要在插入时排序）。
   • 删除操作：O(n)（需要遍历找到最高优先级的元素）。
   • 适用于元素数量较少的情况。

2. 二叉堆（Binary Heap）：

   • 插入操作：O(log n)。
   • 删除操作：O(log n)。
   • 二叉堆是最常用的优先队列实现方式，因为它提供了较好的平衡性。

3. 平衡二叉搜索树（如AVL树、红黑树）：

   • 插入操作：O(log n)。
   • 删除操作：O(log n)。
   • 适用于需要频繁查找和删除的场景。

JavaScript 实现示例

以下是一个使用二叉堆实现的优先队列的简单示例：

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

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

  isEmpty() {
    return this.size() === 0;
  }

  peek() {
    return this._heap[0];
  }

  push(value) {
    this._heap.push(value);
    this._siftUp();
    return this.size();
  }

  pop() {
    if (this.size() > 1) {
      this._swap(0, this.size() - 1);
    }
    const poppedValue = this._heap.pop();
    this._siftDown();
    return poppedValue;
  }

  _parent(index) {
    return Math.floor((index - 1) / 2);
  }

  _leftChild(index) {
    return index * 2 + 1;
  }

  _rightChild(index) {
    return index * 2 + 2;
  }

  _swap(i, j) {
    [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
  }

  _siftUp() {
    let nodeIdx = this.size() - 1;
    while (nodeIdx > 0 && this._compare(nodeIdx, this._parent(nodeIdx))) {
      this._swap(nodeIdx, this._parent(nodeIdx));
      nodeIdx = this._parent(nodeIdx);
    }
  }

  _siftDown() {
    let nodeIdx = 0;
    while (
      (this._leftChild(nodeIdx) < this.size() &&
        this._compare(this._leftChild(nodeIdx), nodeIdx)) ||
      (this._rightChild(nodeIdx) < this.size() &&
        this._compare(this._rightChild(nodeIdx), nodeIdx))
    ) {
      const greaterChildIdx =
        this._rightChild(nodeIdx) < this.size() &&
        this._compare(this._rightChild(nodeIdx), this._leftChild(nodeIdx))
          ? this._rightChild(nodeIdx)
          : this._leftChild(nodeIdx);
      this._swap(nodeIdx, greaterChildIdx);
      nodeIdx = greaterChildIdx;
    }
  }

  _compare(i, j) {
    return this._comparator(this._heap[i], this._heap[j]);
  }
}

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

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

应用场景

1. 任务调度：操作系统中的任务调度器可以使用优先队列来决定下一个要执行的任务。
2. 图算法：如Dijkstra算法和A*算法中，优先队列用于选择下一个要处理的节点。
3. 数据压缩：Huffman编码中使用优先队列来构建最优前缀码。

总结

优先队列是一种非常有用的数据结构，特别适合需要频繁处理优先级最高元素的场景。通过合理选择底层数据结构（如二叉堆），可以高效地实现优先队列的插入和删除操作。在实际开发中，优先队列的应用非常广泛，理解其原理和实现方式对于解决复杂问题非常有帮助。