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字，可根據需要調整示例代碼的詳細程度來精確控制字數）