前言
Priority Queue (優先權佇列) 是一種特殊的 Queue，
在特殊題型上會非常實用。
個人理解後，我自己是不太會把 Priority Queue 當 Queue 看，應用上的內容已經差滿多的了。
只要牽扯到「優先權」的題目，都非常適合用 Priority Queue 來快速解。
例如：排程類題目，重要性(優先序)高的必須要先做，再來做比較不急的事情。
Priority Queue (優先權佇列) 的精神
Priority Queue 當初被設計的時候，就是為了解決重要性問題而設計的 Queue，
他擁有類似 Queue 能「放入任務」、「取出任務」的概念，
不過在「取出任務」的這個部分就不像我們一般認知的那種單純的 Queue。
Priority Queue 依照「重要性」，決定取出的順序，
因此在傳入 Priority Queue 時，我們常會需要「多帶一個能代表重要性的 Key」
範例程式碼
我覺得有時候理解直接閱讀程式碼會比較快啦 XDD
註：在預設的定義中，「數字越小表示越重要」，會先被 get(pop) 出來
無 key 版本，單純以傳入數字排序
from queue import PriorityQueue
q = PriorityQueue()
q.put(4)
q.put(2)
q.put(5)
q.put(1)
q.put(3)
while not q.empty():
next_item = q.get()
print(next_item)
- 結果
1
2
3
4
5
有 key 版本，依照傳入 key 排序
from queue import PriorityQueue
q = PriorityQueue()
q.put((4, 'Read'))
q.put((2, 'Play'))
q.put((5, 'Write'))
q.put((1, 'Code'))
q.put((3, 'Study'))
while not q.empty():
next_item = q.get()
print(next_item)
- 結果
(1, 'Code')
(2, 'Play')
(3, 'Study')
(4, 'Read')
(5, 'Write')
Priority Queue 的底層設計
Priority Queue 是由 Heap 實做的，因此「 與 Queue 在放入與取出資料時的時間複雜度並不相同 」，
也是因為此原因，通常我不太把 Priority Queue 當 Queue 看，
我倒覺得他更像 Heap。
而因為是 Heap 的原因，
插入與取出的時間複雜度皆為 O(logN)，與 Queue 的 O(1) 也非常不同。
Priority Queue 與 Stack, Queue 比較
這邊我把我腦袋中所想的畫出來
而從上圖我們也可以推論
| insert | delete | |
|---|---|---|
| Stack | O(1) | O(1) |
| Queue | O(1) | O(1) |
| Priority Queue | O(logN) | O(logN) |
所以我才說，理解後真的不會把 Priority Queue 當 Queue 看吧XDD