Priority Queue：Intro(簡介)

本篇文章將介紹抽象的資料結構：Priority Queue(優先權佇列)的基本概念。

簡介：Priority Queue(優先權佇列)

「待辦事項」通常是表面上看起來沒有順序、但其實具有「執行時的優先順序」的一堆事情。

Priority Queue(優先權佇列)就像在處理「待辦事項」，能夠在眾多各自具有優先順序之資料堆中，取出「最重要/最不重要」的項目：

Priority：對資料項目賦予「權重/優先權」，用以表示資料的重要程度。
Queue：隊伍、佇列、順序，意味著把資料整理成「某種順序」的資料結構。

所謂的「某種順序」，可能是「先進先出(First-In-First-Out)」順序：每次要從此資料結構讀取資料時，必定是拿到「先進入」該資料結構的資料。
(請參考：Queue: Intro(簡介))
也有可能是額外賦予資料的「權重/優先權」順序：每次要從此資料結構讀取資料時，必定會拿到具有「最大值/最小值權重」的資料。

如果每次要從Priority Queue讀取資料時，都拿到「權重最大」的資料，則稱此為Max-Priority Queue。
反之，若每次讀取資料，都拿到「權重最小」的資料，則稱此為Min-Priority Queue。

舉例來說，如果每天起床固定要：

那麼，以一個Max-Priority Queue來管理「每天起床的待辦事項」，第一件事情要先刷牙上廁所，然後是剪指甲，最後再削一些無關緊要的鉛筆。
反之，若以一個Min-Priority Queue來管理「每天起床的待辦事項」，第一件事情要先削鉛筆，然後是剪指甲，最後才能去刷牙。

一個Max-Priority Queue，最基本會有三種操作：

Insert：將資料加入Queue中。
- 例如，把「削鉛筆」、「梳洗」、「剪指甲」三件事情寫進Queue裡。
IncreaseKey：當某項資料的「重要性提高」時，需要在Queue中改變資料的權重，以下將以Key代表權重。
- 例如，最近突變出某種藉由指甲垢傳遞的流感病毒，使得「剪指甲」的重要性提高，便需要增加「剪指甲」的Key，假設Key提高到\(11\)分，那麼每天起床的工作順序就變成：「剪指甲」、「梳洗」、「削鉛筆」。
ExtractMax：取得最重要(Key最大)的資料，並將其從Queue中移除。
- 每天起床後，先從「待辦事項」得知，最重要的事情是「梳洗」，並在完成之後，將其從「待辦事項」移除，避免重複執行。

與之對應的Min-Priority Queue之基本操作則是：

為了替Prim's Algorithm以及Dijkstra's Algorithm鋪路，本系列文章將以Min-Priority Queue作為代表。
不過只要掌握Priority Queue的概念，Max-Priority Queue就只是桌上的一塊小蛋糕。

稍微困難的是實現方法，Fundamentals of Data Structures in C++, Ch9一共列出了六種實現方法(可能還有更多)：

前四種資料結構稱為Single-End Priority Queue(SEPQ)，亦即，該資料結構只能取得「最大」或是「最小」權重的資料。
後兩種資料結構稱為Double-End Priority Queue(DEPQ)，可以同時取得「權重最大」以及「權重最小」的資料。

下ㄧ篇文章，將介紹比上述六種資料結構更初級的Binary Heap來實現Min-Priority Queue。

回到目錄：