4.4 優先隊列

隊列大量應用在計算機科學以及我們的生活中，我們在之前話題中實現的默認隊列也有一些修改版本。

其中一個修改版就是優先隊列。元素的添加和移除是基於優先級的。一個現實的例子就是機場登機的順序。頭等艙和商務艙乘客的優先級要高於經濟艙乘客。在有些國家，老年人和孕婦（或帶小孩的婦女）登機時也享有高於其他乘客的優先級。

另一個現實中的例子是醫院的（急診科）候診室。醫生會優先處理病情比較嚴重的患者。通常，護士會鑒別分類，根據患者病情的嚴重程度放號。

實現一個優先隊列，有兩種選項：設置優先級，然後在正確的位置添加元素；或者用入列操作添加元素，然後按照優先級移除它們。在這個示例中，我們將會在正確的位置添加元素，因此可以對它們使用默認的出列操作：

function PriorityQueue {
  let items = ;
  function QueueElement (element, priority){ // {1}
    this.element = element;
    this.priority = priority;
  }

  this.enqueue = function(element, priority){
    let queueElement = new QueueElement(element, priority);

    let added = false;
    for (let i=0; i<items.length; i++){
      if (queueElement.priority < items[i].priority){ // {2}
        items.splice(i,0,queueElement); // {3}
        added = true;
        break; // {4}
      }
    }
    if (!added){
      items.push(queueElement); //{5}
    }
  };

  this.print = function{
    for (let i=0; i<items.length; i++){
      console.log(`${items[i].element} -
      ${items[i].priority}`);
    }
  };
  //其他方法和默認的Queue實現相同
}

  

默認的Queue類和PriorityQueue類實現上的區別是，要向PriorityQueue添加元素，需要創建一個特殊的元素（行{1}）。這個元素包含了要添加到隊列的元素（它可以是任意類型）及其在隊列中的優先級。

如果隊列為空，可以直接將元素入列（行{2}）。否則，就需要比較該元素與其他元素的優先級。當找到一個比要添加的元素的priority值更大（優先級更低）的項時，就把新元素插入到它之前（根據這個邏輯，對於其他優先級相同，但是先添加到隊列的元素，我們同樣遵循先進先出的原則）。要做到這一點，我們可以用第2章學習過的JavaScript的array類的splice方法。一旦找到priority值更大的元素，就插入新元素（行{3}）並終止隊列循環（行{4}）。這樣，隊列也就根據優先級排序了。

如果要添加元素的priority值大於任何已有的元素，把它添加到隊列的末尾就行了（行{5}）：

let priorityQueue = new PriorityQueue;
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1);
priorityQueue.print;

  

以上代碼是一個使用PriorityQueue類的示例。在下圖中可以看到每條命令的結果（以上代碼的結果）：

第一個被添加的元素是優先級為2的John。因為此前隊列為空，所以它是隊列中唯一的元素。接下來，添加了優先級為1的Jack。由於Jack的優先級高於John，它就成了隊列中的第一個元素。然後，添加了優先級也為1的Camila。Camila的優先級和Jack相同，所以它會被插入到Jack之後（因為Jack先被插入隊列）；Camila的優先級高於John，所以它會被插入到John之前。

我們在這裡實現的優先隊列稱為最小優先隊列，因為優先級的值較小的元素被放置在隊列最前面（1代表更高的優先級）。最大優先隊列則與之相反，把優先級的值較大的元素放置在隊列最前面。