JavaScript如何实现优先级队列

# JavaScript如何实现优先级队列

## 什么是优先级队列

优先级队列（Priority Queue）是一种特殊的队列数据结构，其中每个元素都关联一个优先级值。与普通队列（先进先出，FIFO）不同，优先级队列中的元素按照优先级顺序出队：优先级高的元素先出队，相同优先级的元素则按入队顺序处理。

### 典型应用场景
- 操作系统进程调度（高优先级任务优先执行）
- 医院急诊分诊（病情严重的患者优先就诊）
- Dijkstra最短路径算法
- 哈夫曼编码
- 事件驱动模拟

## JavaScript实现方案

### 1. 基于数组的简单实现

```javascript
class PriorityQueue {
  constructor() {
    this.items = [];
  }

  // 入队操作 O(n)
  enqueue(element, priority) {
    const queueElement = { element, priority };
    let added = false;
    
    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    
    if (!added) {
      this.items.push(queueElement);
    }
  }

  // 出队操作 O(1)
  dequeue() {
    return this.items.shift();
  }

  // 其他辅助方法
  isEmpty() {
    return this.items.length === 0;
  }
}

优点：实现简单，适合小规模数据
缺点：入队操作时间复杂度为O(n)，性能较差

2. 使用二叉堆实现（最优方案）

二叉堆（Binary Heap）是一种完全二叉树，适合实现优先级队列：

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

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

  // 插入元素 O(log n)
  insert(element, priority) {
    const node = { element, priority };
    this.heap.push(node);
    this.heapifyUp(this.heap.length - 1);
  }

  // 上浮操作
  heapifyUp(index) {
    while (index > 0) {
      const parent = this.parentIndex(index);
      if (this.heap[parent].priority <= this.heap[index].priority) break;
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      index = parent;
    }
  }

  // 提取最小元素 O(log n)
  extractMin() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return min;
  }

  // 下沉操作
  heapifyDown(index) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;
    
    if (left < this.heap.length && 
        this.heap[left].priority < this.heap[smallest].priority) {
      smallest = left;
    }
    
    if (right < this.heap.length && 
        this.heap[right].priority < this.heap[smallest].priority) {
      smallest = right;
    }
    
    if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      this.heapifyDown(smallest);
    }
  }
}

复杂度分析： - 插入操作（enqueue）：O(log n) - 删除操作（dequeue）：O(log n) - 获取最高优先级元素：O(1)

3. 使用第三方库

实际项目中可以考虑使用现成的库：

// 使用 priorityqueuejs 库
const PriorityQueue = require('priorityqueuejs');

const pq = new PriorityQueue((a, b) => b.priority - a.priority);
pq.enq({ value: 'A', priority: 3 });
pq.enq({ value: 'B', priority: 1 });
console.log(pq.deq()); // 输出 { value: 'B', priority: 1 }

完整实现示例

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

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

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

  peek() {
    return this.heap[0]?.element;
  }

  enqueue(element, priority) {
    const node = { element, priority };
    this.heap.push(node);
    this.#siftUp();
    return this;
  }

  dequeue() {
    if (this.isEmpty()) return null;
    if (this.size() === 1) return this.heap.pop().element;
    
    const removed = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.#siftDown();
    return removed.element;
  }

  #siftUp() {
    let index = this.size() - 1;
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.comparator(this.heap[index], this.heap[parent]) >= 0) break;
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      index = parent;
    }
  }

  #siftDown() {
    let index = 0;
    const length = this.size();
    
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;
      let smallest = index;
      
      if (left < length && 
          this.comparator(this.heap[left], this.heap[smallest]) < 0) {
        smallest = left;
      }
      
      if (right < length && 
          this.comparator(this.heap[right], this.heap[smallest]) < 0) {
        smallest = right;
      }
      
      if (smallest === index) break;
      
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

// 使用示例
const pq = new PriorityQueue();
pq.enqueue("感冒", 3);
pq.enqueue("骨折", 1);
pq.enqueue("擦伤", 2);

console.log(pq.dequeue()); // 输出 "骨折"（优先级最高）

性能对比测试

我们对不同实现方案进行性能测试（10,000次操作）：

高级应用技巧

动态优先级调整

class DynamicPriorityQueue extends PriorityQueue {
  constructor() {
    super();
    this.elementIndices = new Map(); // 元素到索引的映射
  }

  enqueue(element, priority) {
    if (this.elementIndices.has(element)) {
      this.updatePriority(element, priority);
      return;
    }
    super.enqueue(element, priority);
    this.elementIndices.set(element, this.size() - 1);
  }

  updatePriority(element, newPriority) {
    const index = this.elementIndices.get(element);
    const oldPriority = this.heap[index].priority;
    this.heap[index].priority = newPriority;
    
    if (this.comparator({priority: newPriority}, {priority: oldPriority}) < 0) {
      this.#siftUp(index);
    } else {
      this.#siftDown(index);
    }
  }
}

多条件优先级比较

const multiPriorityComparator = (a, b) => {
  // 第一优先级：紧急程度
  if (a.urgency !== b.urgency) return a.urgency - b.urgency;
  // 第二优先级：到达时间
  return a.arrivalTime - b.arrivalTime;
};

const pq = new PriorityQueue(multiPriorityComparator);

常见问题解答

Q：优先级队列和普通队列有什么区别？ A：普通队列严格遵循FIFO原则，而优先级队列根据元素的优先级决定出队顺序。

Q：什么时候应该使用优先级队列？ A：当处理元素的顺序需要根据特定优先级而非插入时间决定时，如任务调度、路径查找等场景。

Q：JavaScript有内置的优先级队列吗？ A：目前JavaScript标准库中没有直接提供优先级队列实现，需要自行实现或使用第三方库。

总结

本文详细介绍了在JavaScript中实现优先级队列的多种方法，从简单的数组实现到高效的二叉堆方案。对于大多数应用场景，基于二叉堆的实现（时间复杂度O(log n)）是最佳选择。实际开发中，可以根据具体需求选择自行实现或使用成熟的第三方库。

”`

（注：实际字数为约2100字，可根据需要调整示例代码的详细程度来精确控制字数）