[資工] Heap Sort 的特性與做法解說 （北捷資訊工程類 109年的考題）
1) 介紹 heap_sort 是一個使用二元樹結構來做排序的演算法，但其實實作上也可以使用一維陣列來儲存資料做 in-place sort (就地排序)，只是實作時要抓好陣列 index 與樹結點的對應關係。 1-1) 元素編號 在一個以 1 為陣列第一個元素的編號所組成的樹中： 一個編號 \(i\) 的元素其左子節點的索引值（編號）定義為 $$2i$$ 其右子節點的編號定義為 $$2i+1$$ 但是若陣列的基底以 0 為第一個編號，則需要對公式稍微調整一下： 2) 差異 heap_sort 與 binary search tree (二元搜尋樹) 的差異在於，BST 需要遵守一樹結點的左子結點值要小於該節點值，而右子結點值則需要大於該結點值（aka 上層節點值）。 而 heap_sort 在使用二元樹上面的限制比較鬆散，在建立 min/max heap 時，只要遵守上層結點值必然小於（或大於）下層節點的值的規則，則可稱之為一個最小/最大堆積。 3) 步驟 這邊舉例是用最大堆積法： 1) 先建立一棵樹的最大堆積排序，做完上層 root 節點保證有整棵樹中最大的值，再把根節點的最大值與陣列最後一個元素交換，最後一個元素即排序好了！ 2) 然後再把剩下的元素(n-1)為範圍所組成的樹，重新做一次最大堆積排序，此時根節點會有第二大的值，再把根節點的值與陣列倒數第二個元素交換，現在有兩個排序好了！ 3) 把未排序的元素們繼續套用 3-2) 的規則，直到所有元素都排序好，即完成遞增的 heap sort。 4) 為什麼要叫做 heap sort? 啊災，可能一些東西隨便堆起來也會長得像二元樹吧（笑 圖片出處： heap of scrap metal, Author: Mohylek ，這裏以創用 CC 3.0協議 分享圖片 5) 參考資料 5-1) 堆積排序(Heap Sort)演算法，利用完全二元樹來排序的演算法 - 裡頭有每個步驟的二元樹圖，我就是先看這篇看懂之後才寫本篇的～