[資工] 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?
啊災，可能一些東西隨便堆起來也會長得像二元樹吧（笑
留言
張貼留言