# 堆積排序

## 簡介

堆積排序法是使用完全二元樹(complete binary tree)來進行排序的演算法，利用比較父節點和其左右子節點的大小來進行排序。

### 堆積樹

堆積樹通常有兩種資料結構的實現，一種是使用陣列(Array)，另一種則是使用鍊錶(Linked List)作為資料結構。

堆積樹又分為兩種堆:
1. 最大堆：由最大排列到最小的堆積樹 (父節點為最大)
3. 最小堆：由最小排列到最大的堆積樹 (父節點為最小)

## 詳細步驟

1. 先找出堆積樹的中間節點，即 (n / 2)
2. 從中間節點開始，遞歸到根節點為止，每個節點進行比較排序，分為兩種比較法：
- **最大堆比較**
1. 先找出左右子節點的位置 [left: root * 2] [right: root * 2 + 1]
2. 記得比較確認 left 和 right 是否小於 n
3. 選舉出最大的那個節點，讓他變成父節點
4. 因為交換了節點，會失去最大堆屬性的排序，所以需要再從父節點開始，遞歸以下的所有子節點，在排序一次，直到恢復最大堆屬性為止
3. 如果需要最小堆排序，則需要再進行一次從最大堆到最小堆的轉換

## 參考資料
- [ithome](https://ithelp.ithome.com.tw/articles/10266206)
- [堆積排序法](http://notepad.yehyeh.net/Content/Algorithm/Sort/Heap/Heap.php)