重念一次早該補起來的「資料結構與演算法」。這篇筆記 Heap Sort 的時間複雜度分析。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29828
本篇範圍：Chapter 7
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
回頭複習一下， Heap Sort 的內容。簡言之分成三步驟：
1. 產生一個 Max Heap 的樹狀結構
2. 將產出的樹狀結構的最父層根節點，與樹狀結構最右方最尾端的節點 (陣列最尾巴) 進行替換。
a. 替換到最尾巴的值，代表已排序完成。因此 heapSize 需減 1
1. 產生一個 Max Heap 的樹狀結構
2. 將產出的樹狀結構的最父層根節點，與樹狀結構最右方最尾端的節點 (陣列最尾巴) 進行替換。
a. 替換到最尾巴的值，代表已排序完成。因此 heapSize 需減 1
b. 替換到根節點的值並不一定符合 Max Heap 的要求，所以還有重新生成一個 Max Heap 結構
因此 Heap Sort 的時間複雜度多為 O(nlogN)，最佳時可為 O(n)。因為 MaxHeapify 的執行次數會隨著 Max Heap 的層數(高度)來決定。當你今天所有節點的值都是一樣的時候，MaxHeapify 就不需要執行，那就會是 O(n)。
