優先隊列詳解

優先隊列（Priority Queue）是一種抽象數據類型，它和普通隊列（Queue）的區別在於，每個元素都有一個優先級，並且按照優先級的高低來決定元素的出隊順序。優先隊列可以使用數組、鏈表、堆等結構來實現。

一、基本介紹

優先隊列的基本操作包括：

• Insert：將一個元素加入隊列
• Remove：刪除隊列中優先級最高的元素
• Peek：查看隊列中優先級最高的元素

我們可以使用一個數組來實現優先隊列，每個元素存儲元素的值和優先級，然後根據優先級對數組進行排序。但是這種實現方法的時間複雜度為O(nlogn)，不夠高效。更高效的實現方法是使用堆結構來實現。

二、堆結構

堆是一種完全二叉樹，滿足以下兩個條件：

• 父節點的值總是大於（或小於）它的子節點的值
• 除了最下面一層，其他層的節點都是滿的

堆分為大根堆（Max Heap）和小根堆（Min Heap），在大根堆中，父節點的值總是大於它的子節點的值，在小根堆中，父節點的值總是小於它的子節點的值。

三、優先隊列實現

我們可以使用一維數組來表示堆，如果一個節點的位置是index：

• 它的父節點的位置是(index-1)/2
• 它的左子節點的位置是2*index+1
• 它的右子節點的位置是2*index+2

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

  // 獲取父節點的位置
  parent(index) {
    return Math.floor((index - 1) / 2);
  }

  // 獲取左子節點的位置
  leftChild(index) {
    return 2 * index + 1;
  }

  // 獲取右子節點的位置
  rightChild(index) {
    return 2 * index + 2;
  }

  // 交換兩個元素的位置
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }

  // 插入一個元素到堆中
  insert(value, priority) {
    const newNode = {value, priority};
    this.heap.push(newNode);
    this._heapifyUp();
  }

  // 彈出優先級最高的元素
  remove() {
    if (this.heap.length === 1) return this.heap.pop();
    const topPriority = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._heapifyDown();
    return topPriority;
  }

  // 獲取優先級最高的元素
  peek() {
    return this.heap[0];
  }

  // 上移一個節點，維護堆的性質
  _heapifyUp() {
    let current = this.heap.length - 1;
    while (current > 0 && this.heap[current].priority > this.heap[this.parent(current)].priority) {
      this.swap(current, this.parent(current));
      current = this.parent(current);
    }
  }

  // 下移一個節點，維護堆的性質
  _heapifyDown() {
    let current = 0;
    let maxChildIndex = this.leftChild(current);
    while (maxChildIndex < this.heap.length) {
      if (this.rightChild(current)  this.heap[maxChildIndex].priority) {
        maxChildIndex = this.rightChild(current);
      }
      if (this.heap[current].priority >= this.heap[maxChildIndex].priority) break;
      this.swap(current, maxChildIndex);
      current = maxChildIndex;
      maxChildIndex = this.leftChild(current);
    }
  }
}

四、應用場景

優先隊列的應用場景非常廣泛，可以用來解決很多有優先級的問題。例如：

• 操作系統調度進程
• 任務調度
• 網絡傳輸中的流量控制
• 負載均衡
• 數據壓縮
• Dijkstra算法
• Huffman編碼

五、總結

優先隊列是一種很重要的數據結構，它的實現方法有很多種，其中使用堆結構的實現方法最高效。在實際應用中，優先隊列可以幫助我們解決很多有優先級的問題，它的應用場景非常廣泛。掌握優先隊列的基本操作和實現方法，對於開發人員來說是十分重要的。