---
# System prepended metadata

title: HeapSort
tags: [Algorithm, HeapSort]

---

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

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

完全二元樹可由陣列表示:由上而下由左而右從0開始
![](https://i.imgur.com/kNuOwak.png)
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後
再次得到最大的值,直到完全取出