Priority Queues

第 3.10.4 章：優先隊列 (Priority Queues)

歡迎來到進階數據結構單元！你已經掌握了堆疊 (Stacks, LIFO) 和標準隊列 (Queues, FIFO)。現在，我們要學習一種完全不在乎你何時到達，只在乎你「有多重要」的結構！這就是優先隊列 (Priority Queue)。

理解優先隊列非常重要，因為它們是許多路由、排程和高效數據處理等複雜演算法的基礎。

---

1. 什麼是優先隊列？

優先隊列是一種進階數據結構，其中元素被移除（提取）的順序完全取決於元素的優先級 (priority)，而不是它們抵達的時間。

它的運作像個隊列，但它完全打破了「先進先出」(FIFO) 的規則。

類比：醫院急症室（分流制度）

想像一下你來到急症室。你不會因為先到就先獲得治療，相反地，分流護士會評估你的情況並分配優先級：

• 病人 1（上午 9:00 到達）- 腳趾骨折（低優先級：3）
• 病人 2（上午 9:15 到達）- 胸痛（高優先級：1）
• 病人 3（上午 9:30 到達）- 輕微燙傷（中優先級：2）

儘管病人 1 最先到達，但病人 2（優先級 1）會排在所有人之前接受診治。優先隊列確保了最緊急的案例總是能被優先處理。

核心規則：最高優先級的元素永遠是下一個被取出（Dequeue）的項目。

注意：如果兩個項目的優先級相同，它們通常會遵循標準的 FIFO 規則，按先後順序處理。

2. 優先隊列的操作

就像標準隊列一樣，核心操作包括新增項目和移除項目。

2.1. 新增項目 (Enqueue)

當你對一個項目執行 Enqueue 操作時，必須為其指定一個優先級數值。該項目在底層結構（如陣列）中的儲存位置，取決於你如何實作該隊列以維持優先級順序。

範例：Enqueue (項目: "發送電子郵件", 優先級: 5)

2.2. 移除項目 (Dequeue)

Dequeue 操作會移除並返回目前優先級最高的項目。

範例：如果項目 "系統嚴重警報" 的優先級為 10，且沒有其他項目的優先級達到 10，則無論它是何時加入的，都會優先被 Dequeue。

3. 使用一維陣列實作

課程要求我們了解如何使用一維陣列 (one-dimensional array) 來實作優先隊列。

由於陣列本身並不理解「優先級」的概念，我們必須建立一套結構或規則，將優先級邏輯強加在陣列儲存上。

設計決策：如何儲存數據？

當使用陣列作為優先隊列時，處理數據與優先級配對主要有兩種方式：

選項 1：未排序陣列 (Unsorted Array)（Enqueue 較簡單，Dequeue 較慢）

項目僅僅被加入到陣列中下一個可用的位置（就像標準的線性隊列）。這非常快（時間複雜度為 O(1)）。

• Enqueue： 加到末端。
• Dequeue： 為了移除優先級最高的項目，演算法必須掃描*整個*陣列以找出優先級最高的項目。這比較慢（時間複雜度為 O(n)，其中 \(n\) 為項目的數量）。

選項 2：已排序陣列 (Sorted Array)（Enqueue 較慢，Dequeue 較快）

項目插入陣列時，陣列會始終保持按優先級排序（例如：最高優先級的項目永遠位於索引 0）。當檢索效率至關重要時，這是更常見的做法。

• Enqueue（新增）： 當新項目到達時，我們必須根據其優先級找到正確的位置，並將所有較低優先級的項目向後移動以騰出空間。這可能較慢（O(n)）。
• Dequeue（移除）： 確保最高優先級的項目位於固定位置（通常是前端/起始索引）。移除非常快（O(1)）。

如果剛開始覺得有點複雜，別擔心！核心概念就是管理陣列指標，以確保我們遵守優先級順序。

3.1. 實作檢查（判斷空或滿）

無論陣列是已排序還是未排序，檢查隊列狀態都需要追蹤用於管理陣列的指標或索引。

在陣列中實作隊列結構時，我們通常會使用三個變數：

• QUEUE_ARRAY：儲存數據的一維陣列。
• Size：陣列的最大容量。
• Count（或像 Front/Rear 的指標）：追蹤目前隊列中的項目數量。

測試優先隊列是否為空 (Empty)

如果儲存的項目數量為零，則以陣列實作的優先隊列即為空。

實作檢查（使用 Count 變數）：
IF Count == 0 THEN Queue_is_Empty

測試優先隊列是否已滿 (Full)

如果儲存的項目數量等於陣列的最大容量，則以陣列實作的優先隊列即為滿。

實作檢查（使用 Count 變數）：
IF Count == Size THEN Queue_is_Full

4. 優先隊列的合適應用

每當資源管理或順序處理必須基於重要性而非時間先後順序時，優先隊列就是不可或缺的。

• 作業系統排程： 管理處理程序。關鍵的系統處理程序（例如處理中斷或錯誤）必須在背景任務（例如磁碟重組）之前執行，即使背景任務更早提交。
• 事件模擬： 在模擬中，事件必須按照預定時間的先後順序處理，這可以視為一種優先級（時間最早 = 最高優先級）。
• 頻寬管理： 優先處理網絡封包。重要的數據封包（如視訊會議流量）應該比較不重要的數據（如大檔案下載）更早發送。
• 圖論演算法： 優先隊列用於實作某些關鍵的圖論演算法。

你知道嗎？

最短路徑演算法——戴克斯特拉演算法 (Dijkstra’s algorithm)，很大程度上依賴優先隊列來高效選擇下一個要訪問的節點；它總是優先考慮與起點累計距離最短的節點，實際上就是將距離視為優先級！

重點總結

優先隊列根據指定的優先級數值來處理項目。雖然使用一維陣列實作很簡單，但這通常需要不斷地移動元素或搜尋來維持優先級順序。對於需要按重要性處理任務的系統來說，它是至關重要的。