Python實作排序演算法-堆積排序法(Heap Sort)

Heap sort是一種在所以有情況下的時間複雜度都能維持在N log N的排序演算法，算一種效率相當好的排序演算法，我們會以Python實作此演算法。

Skiptocontent Heapsort是一種在所以有情況下的時間複雜度都能維持在NlogN的排序演算法，算一種效率相當好的排序演算法，我們會以Python實作此演算法。

演算法分析 簡單來說，此演算法主要可分解為以下幾個步驟 建構(Heapify):將陣列轉換成Maxheap或Minheap調整(Adjust):進行排序交換節點:將root的值與最後一個節點交換刪除節點:將最後一個節點刪除，因為已經排序完成 Maxheap與Minheap的差別在於Maxheap就是父節點會大於或等於子節點，Minheap則相反，應用上，如果今天要遞增排序，就會使用Maxheap，反之，則會使用Minheap。

Maxheap與Minheap 建構(Heapify) 簡單來說就是將要排序的陣列轉換成為完整二元樹(completebinarytree) 我們假設要來排序此陣列:[5,10,2,7,1] 將其轉換成二元樹 將陣列轉換成完整二元樹 調整(Adjust) 調整即是將完整二元樹轉換成Maxheap，簡單來說就是要將父節點之值>=子節點之值，因此我們可以從中間的節點往上開始檢查，每當父值=子值時就停止，再往上一個找，直到到達根部(root)，就代表maxheap建構完成。

根據我們剛剛的排序陣列:[5,10,2,7,1]，有5個元素，因此會從5/2也就是第2個的位置開始找，因為第2個位置之後的值就沒有子值了，代表沒有比較的必要，因此可以省略不找。

從上圖，我們可以看到父值>子值們，因此不需調整，可以再往2上一個找，也就是第1個值(root)。

根據上圖，我們可以看到父值5