筆記 - Priority Queue (PQ)

Posted on In

Concepts

  1. Priority Queue (PQ)是一種概念，比起regular queue，元素多了一個“priority 優先順序”的性質
  2. Priority數字越大 => 優先程度越高
  3. 這個概念可用於各種資料結構中，其中以Max Heap最有效率

Max Heap: Binary tree. 其中parent node一定比兩邊的child nodes大。（左右兩邊child nodes誰大誰小則不一定）

Big O of Enqueue and Dequeue

  • Max Heap:
    • Enqueue O(log n)
    • Dequeue O(log n)
  • Array or Linked List:
    • Enqueue O(n) (insertion sort for a nearly sorted array)
    • Dequeue O(1) - Linked List; O(n)- Array

Idea

Priority Queue為動態的，加入/移除新元素後，檢查新元素與parent node大小，若新元素較大，則將parent node與new node互換

Pseudocode of PQ Enqueue

1
2
3
4
5
6
7
8
9
10
11
12
13
ENQUEUE (value, priority)
  if PQ is empty:
    add node into PQ
  else: 
    push node into PQ
    newNodeIndex = PQ.length - 1
    parentNodeIndex = Math.floor((newNodeIndex - 1) / 2)
    // 檢查大小
    while (parentIndex >= 0) && (newNode.priority > parentNote.priority):
      swap parentNode and newNode
      // update index number after swapping
      newNodeIndex = parentIndex
      parentIndex = Math.floor((newNodeIndex - 1) / 2)

Pseudocode of PQ Dequeue

1
2
3
4
5
6
7
8
9
10
DEQUEUE ()
  if PQ.length = 0
    return false
  if PQ.length = 1
    remove PQ[0]
    return PQ[0]
  else: // 如果PQ內有兩個以上的元素
    swap PQ[0] and PQ[PQ.length - 1] // 第一個元素與最後一個元素互換
    PQ.pop() // 移除最後一個元素
    maxHeapify() // 剩下的元素作MH

這樣跑完可以讓最優先處理的元素被排在第一個(MH結構)
maxHeapify() 要回去看Heap Sort內容

Code

Repl