# HeapSort
###### tags: `Algorithm` `HeapSort`
使用時機 : 當需要的是與排序有關聯的東西時ex 最大最小值 , top K ,需要在一组不停更新的数据中不停地找最大/小元素

完全二元樹 : 樹的組成為由上而下由左而右
heapify : 二元樹的parent節點的值 大於/小於 兩個child節點的值
heap : 為heapify後的完全二元樹

完全二元樹可由陣列表示:由上而下由左而右從0開始
int i [] = {10,5,8,3,4,6,7,1,2}
用陣列表示的優勢是可以透過計算取得父節點或子節點
parret = ( idx - 1 )/2
child1 = 2idx+1
child2 = 2idx+2
將一個完全二元樹heapify的順序為由下而上由右而左
以上圖為例則是[3,1,2] -> [8,6,7] -> [5,3,4] -> [10,5,8]
並且需檢查交換後child是否還為heap

Heap sort
以max heap來舉例
當該tree為完全二叉樹且heapify時,最頂層為最大的值
排序過程為 : 將最頂層的值與"最後一個"值交換
並且將最後一個值砍掉(取出)後,對剩下的樹進行heapify後
再次得到最大的值,直到完全取出