重念一次早該補起來的「資料結構與演算法」。這篇筆記優先序列 ( Priority Queue ) 的簡介。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29877
本篇範圍：Chapter 9
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
1. 「優先序列」是一種抽象的資料結構。與一般的 Queue 相比，每一個元素多了一個 priority 的屬性
2. 若一個元素它的 priority 的屬性較高，那會優先被處理
3. 實作方式可以用 Linked List, Queue, Array…等，但最有效率的是 Max Heap – 也就是一個二元樹的父節點要比其下的左右節點都來得大。不過左右節點間的大小比較就不重要。
4. 當使用 Max Heap 的結構來實作優先序列，那 Enqueue 和 Dequeue 都會是 O(logN)；若用 Array 或是 Linked List，那在 Enqueue 會是 O(n), Dequeue 會是 O(1) 或是 O(n)
5. Max Heap Insertion 的過程會等同於 Heap Sort 的由小到大排序。
因為在執行完第一次的 Heap Sort 後，你會將第一個值與最後一個值互換(相當於優先處理)，然後將待處理的資料量減 1。接著再執行一次 Heap Sort，然後重複執行上述步驟直到全部完成。
系列文章
[blogimove-CPC-TAG=theIdeaOfAlgorithm-MODE=1-POSTNUM=-ORDERBY=title-ORDERTYPE=desc]
按讚加入粉絲團
