Priority Queue(優先佇列)

介紹

Priority Queue是一種特殊類型的資料結構，其中每個元素都有一個與之關聯的優先級或權重，並且根據其優先級來決定存取和刪除元素的順序。不同於一般的佇列（Queue），Priority Queue不一定是先進先出（FIFO）的，而是根據元素的優先級來決定處理的順序。

優先級該如何比較? 優先級通常根據事先定義的比較函數（Comparator）或物件本身的內部屬性來決定，並且越小或越大的元素視為優先級越高，取決於具體的實現方式。

Priority Queue在許多應用場景中都是非常有用的，例如作業系統中的進程調度、路由協議中的路徑選擇、圖形算法中的最小生成樹、現實生活中醫院急診室中的病人。

Priority Queue通常支持以下基本操作：

• 插入（Insertion）：將一個新的元素插入到Priority Queue中，並根據其優先級進行排序。
• 刪除最大/最小元素（Deletion）：刪除Priority Queue中具有最高/最低優先級的元素，並返回其值。
• 查找最大/最小元素（Peek）：獲取Priority Queue中具有最高/最低優先級的元素的值，但不刪除它。
• 更新元素的優先級（Update）：在Priority Queue中修改某個元素的優先級，並重新排序。

複雜度

時間複雜度

實現	插入Enqueue	刪除Dequeue
Max Heap	$O(logn)$	$O(logn)$
LinkedList	$O(n)$	$O(1)$
Array	$O(n)$	$O(n)$

陣列實現

依序實現以下功能:

• 插入（enqueue）：O(1)（如果數組的大小充足，否則需要擴展數組，時間複雜度為O(n)）
• 刪除最大或最小元素（dequeue）：O(n)（因為需要重新排列數組中的元素）
• 查詢最大或最小元素（peek）：O(1)

初始化

首先先定義一個 PriorityQueueNode 類別，這個類別有兩個屬性 value 和 priority，分別代表節點的值和優先級。

接著，定義了 PriorityQueue 類別，這個類別有一個屬性 queue，它使用一個陣列來實現優先佇列。在這個優先佇列中，元素是按照優先級排序的，優先級高的元素會被先取出。

// 定義優先佇列的節點類別
class PriorityQueueNode {
  constructor(value, priority) {
    this.value = value;       // 節點的值
    this.priority = priority; // 節點的優先級
  }
}

// 定義優先佇列類別
class PriorityQueue {
  constructor() {
    this.queue = []; // 使用陣列來實現優先佇列
  }
}

插入（enqueue）

接下來新增的是 PriorityQueue 類別中的 enqueue 方法，用於向優先佇列中插入一個新的節點。

這個方法接受兩個參數：value 表示要插入節點的值，priority 表示要插入節點的優先級。該方法根據優先級的大小將新節點插入到適當位置。

// 插入操作enqueue
enqueue(value, priority) {
  const newNode = new PriorityQueueNode(value, priority); // 創建新的節點
  let inserted = false; // 用於標記是否已經插入新節點

  for (let i = 0; i < this.queue.length; i++) {
    if (newNode.priority < this.queue[i].priority) { // 比較優先級
      this.queue.splice(i, 0, newNode); // 將新節點插入到適當位置
      inserted = true;
      break;
  }
}

  if (!inserted) {
    this.queue.push(newNode); // 若未插入，則將新節點添加到佇列末尾
  }
}

刪除最大或最小元素（dequeue）

從優先佇列中取出優先級最高的節點。如果佇列為空，則返回 null。

// 出隊操作dequeue
dequeue() {
  if (this.isEmpty()) {
    return null; // 若佇列為空，則返回null
  }

  return this.queue.shift(); // 移除佇列頭部的節點並返回其值
}

查詢最大或最小元素（peek）

查看優先佇列中優先級最高的節點的值，但不將其從佇列中移除。如果佇列為空，則返回 null。

peek() {
  if (this.isEmpty()) {
    return null;
  }
    return this.queue[0];
}

完整程式碼

// 定義優先佇列的節點類別
class PriorityQueueNode {
  constructor(value, priority) {
    this.value = value;       // 節點的值
    this.priority = priority; // 節點的優先級
  }
}

// 定義優先佇列類別
class PriorityQueue {
  constructor() {
    this.queue = []; // 使用陣列來實現優先佇列
  }

  // 插入操作enqueue
  enqueue(value, priority) {
    const newNode = new PriorityQueueNode(value, priority); // 創建新的節點
    let inserted = false; // 用於標記是否已經插入新節點

    for (let i = 0; i < this.queue.length; i++) {
      if (newNode.priority < this.queue[i].priority) { // 比較優先級
        this.queue.splice(i, 0, newNode); // 將新節點插入到適當位置
        inserted = true;
        break;
      }
    }

    if (!inserted) {
      this.queue.push(newNode); // 若未插入，則將新節點添加到佇列末尾
    }
  }
    
  // 出隊操作dequeue
  dequeue() {
    if (this.isEmpty()) {
      return null; // 若佇列為空，則返回null
    }

    return this.queue.shift(); // 移除佇列頭部的節點並返回其值
  }
  
  // 查詢優先級最高元素
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.queue[0][0];
  }    

  // 更新元素
  update(value, newPriority) {
    let found = false; // 用來標記是否找到待更新的元素

    // 在佇列中尋找待更新的元素
    for (let i = 0; i < this.queue.length; i++) {
      if (this.queue[i].value === value) {
        // 找到待更新的元素
        this.queue[i].priority = newPriority; // 更新優先級

        found = true; // 標記已找到
        break; // 停止尋找
      }
    }

    if (!found) {
      // 若未找到待更新的元素，則返回null
      return null;
    }

    // 將佇列重新排序以維持優先級順序
    this.queue.sort((a, b) => a.priority - b.priority);
  }

  // 判斷佇列是否為空
  isEmpty() {
    return this.queue.length === 0;
  }
}

Max Heap實現

依序實現以下功能:

• 插入（enqueue）：$O(logn)$
• 刪除最大或最小元素（dequeue）：$O(logn)$
• 查詢最大或最小元素（peek）：O(1)

補充

在堆積(Heap)中如何找到節點的child node或是parent node索引位置呢?

• child node 索引位置等於$x => (2x+1, 2x+2)$
• parent node 索引位置等於$x => Math.floor((x-1)/2)$

查看以下範例，範例為一顆Max Heap:

假設要求節點6的 child node 以及 parent node 索引位置該怎麼尋找?讓我們將以上公式帶入

// child node
let x = 1;
let childNode = [2x+1, 2x+2] // [3, 4]

// parent node
let x = 1;
let parentNode = Math.floor((1-1)/2) // 0

Enqueue

虛擬碼

ENQUEUE(value, priority):
  if PQ is empty:	
    add node into PQ
  else:		
    push node into PQ
    newIndex = PQ.length – 1	
    parentIndex = Math.floor(newIndex - 1 / 2)	
    while (parentIndex >= 0) and newNode.priority > parent.priority:		
      swap parent and child		
      newIndex = parentIndex		
      parentIndex = Math.floor(newNodeIndex - 1 / 2)

程式碼

class Node {
    constructor(value, priority) {
        this.value = value;
        this.priority = priority;
    }
}

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

    enqueue(value, priority) {
        let node = new PQNode(value, priority);
        if (this.values.length == 0) {
            this.values.push(node)
        } else {
            this.values.push(node);
            let newIndex = this.values.length - 1
            let parentIndex = Math.floor((newIndex - 1) / 2)
            while (parentIndex >= 0 && this.values[newIndex].priority > this.values[parentIndex].priority) {
                [this.values[parentIndex], this.values[newIndex]] = [this.values[newIndex], this.values[parentIndex]];
                newIndex = parentIndex
                parentIndex = Math.floor((newIndex - 1) / 2)
            }
        }
    }
}

Dequeue

虛擬碼

DEQUEUE():
  if PQ.length == 0:	
    return false
  if PQ.length == 1:	
    remove PQ[0]
    return PQ[0]
  else:	
    swap PQ[0] and PQ[PQ.length - 1]
    PQ.pop()
    maxHeapify(0)

程式碼

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

    dequeue() {
        if (this.isEmpty()) {
            return false
        }
        if (this.values.length == 1) {
            return this.values.shift();
        } else {
            [this.values[0], this.values[this.values.length - 1]] = [this.values[this.values.length - 1], this.values[0]]
            let max = this.values.pop();
            this.maxHeapify(0);
            return max;
        }
    }

    maxHeapify(i) {
        let largest;
        let l = i * 2 + 1;
        let r = i * 2 + 2;
        if (l < this.values.length - 1 && this.values[l].priority > this.values[i].priority) {
            largest = l;
        } else {
            largest = i;
        }

        if (r <= this.values.length - 1 && this.values[r].priority && this.values[largest].priority) {
            largest = r;
        }

        if (largest != i) {
            [this.values[i], this.values[largest]] = [this.values[largest], this.values[i]]
            maxHeapify(largest);
        }
    }

    isEmpty() {
        return this.values.length == 0;
    }
}

完整程式碼

class Node {
    constructor(value, priority) {
        this.value = value;
        this.priority = priority;
    }
}

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

    enqueue(value, priority) {
        let node = new Node(value, priority);
        if (this.values.length == 0) {
            this.values.push(node)
        } else {
            this.values.push(node);
            let newIndex = this.values.length - 1
            let parentIndex = Math.floor((newIndex - 1) / 2)
            while (parentIndex >= 0 && this.values[newIndex].priority > this.values[parentIndex].priority) {
                [this.values[newIndex], this.values[parentIndex]] = [this.values[parentIndex], this.values[newIndex]];
                newIndex = parentIndex
                parentIndex = Math.floor((newIndex - 1) / 2)
            }
        }
    }

    dequeue() {
        if (this.isEmpty()) {
            return false
        }
        if (this.values.length == 1) {
            return this.values.shift();
        } else {
            [this.values[0], this.values[this.values.length - 1]] = [this.values[this.values.length - 1], this.values[0]]
            let max = this.values.pop();
            this.maxHeapify(0);
            return max;
        }
    }

    maxHeapify(i) {
        let largest;
        let l = i * 2 + 1;
        let r = i * 2 + 2;
        if (l < this.values.length - 1 && this.values[l].priority > this.values[i].priority) {
            largest = l;
        } else {
            largest = i;
        }

        if (r <= this.values.length - 1 && this.values[r].priority && this.values[largest].priority) {
            largest = r;
        }

        if (largest != i) {
            [this.values[i], this.values[largest]] = [this.values[largest], this.values[i]]
            maxHeapify(largest);
        }
    }

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

    isEmpty() {
        return this.values.length == 0;
    }
}

let pq = new PriorityQueue();
pq.enqueue("A", 1);
pq.enqueue("B", 2);
pq.enqueue("C", 3);
pq.dequeue()
console.log(pq.peek());

console.log(pq.values)

範例二

class PriorityQueueNode {
  constructor(value, priority) {
    this.value = value;
    this.priority = priority;
  }
}

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

  enqueue(value, priority) {
    const node = new PriorityQueueNode(value, priority);
    this.heap.push(node);
    this.bubbleUp(this.heap.length - 1);
  }

  dequeue() {
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.bubbleDown(0);
    }
    return max.value;
  }

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

  bubbleUp(index) {
    const node = this.heap[index];
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parent = this.heap[parentIndex];
      if (node.priority <= parent.priority) break;
      this.heap[index] = parent;
      index = parentIndex;
    }
    this.heap[index] = node;
  }

  bubbleDown(index) {
    const node = this.heap[index];
    const length = this.heap.length;
    while (true) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild.priority > node.priority) {
          swap = leftChildIndex;
        }
      }
      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if (
          (swap === null && rightChild.priority > node.priority) ||
          (swap !== null && rightChild.priority > leftChild.priority)
        ) {
          swap = rightChildIndex;
        }
      }
      if (swap === null) break;
      this.heap[index] = this.heap[swap];
      index = swap;
    }
    this.heap[index] = node;
  }
}

鏈結串列(Linked list)實現

• 插入（enqueue）：$O(n)$(當新節點的優先級比所有已有節點的優先級都大時)
• 刪除最大或最小元素（dequeue）：$O(1)$
• 查詢最大或最小元素（peek）：$O(1)$

class PriorityQueueNode {
  constructor(value, priority) {
    this.value = value;
    this.priority = priority;
    this.next = null;
  }
}

class PriorityQueue {
  constructor() {
    this.head = null;
  }

  enqueue(value, priority) {
    const newNode = new PriorityQueueNode(value, priority);

    if (this.isEmpty()) {
      this.head = newNode;
    } else if (newNode.priority < this.head.priority) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let current = this.head;

      while (current.next !== null && current.next.priority <= newNode.priority) {
        current = current.next;
      }

      newNode.next = current.next;
      current.next = newNode;
    }
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }

    const value = this.head.value;
    this.head = this.head.next;
    return value;
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.head.value;
  }

  isEmpty() {
    return this.head === null;
  }
}