### 基本原理
利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大于其父節點的值，即A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。堆排序算法就是抓住了堆的這一特點，每次都取堆頂的元素，將其放在序列最后面，然后將剩余的元素重新調整為最大堆，依次類推，最終得到排序的序列。
* * * * *
### 動畫演示
* * * * *
### 算法步驟
1. 創建一個堆 H[0...n-1]；
2. 把堆首（最大值）和堆尾互換；
3. 把堆的尺寸縮小1，并調用 shift_down(0)，目的是把新的數組頂端數據調整到相應位置；
4. 重復步驟 2，直到堆的尺寸為 1；
* * * * *
### 代碼實現
```
function heapAdjust(&$arr, $s, $m) {
$tmp = $arr[$s];
// 在調整為大根堆的過程中可能會影響左子堆或右子堆
// 循環的作用是要保證子堆也是大根堆
for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) {
// 找到根節點的左右孩子中的最大者，然后用這個最大者與根節點比較，
// 若大則進行調整，否則符合大根堆的 特點跳出循環
if($j < $m && $arr[$j] < $arr[$j+1]) {
$j++;
}
if($tmp >= $arr[$j] ) {
break;
}
$arr[$s] = $arr[$j];
$s = $j;
}
$arr[$s] = $tmp;
}
// 堆排序
function heapSort($arr) {
$len = count($arr);
// 依次從子堆開始調整堆為大根堆
for($i = floor($len/2-1); $i >= 0; $i--) {
heapAdjust($arr, $i, $len-1);
}
// 依次把根節點調換至最后一個位置，再次調整堆為大根堆，找到次最大值，
// 依次類推得到一個有序數組
for($n = $len-1; $n > 0; $n--) {
$tmp = $arr[$n];
$arr[$n] = $arr[0];
$arr[0] = $tmp;
heapAdjust($arr, 0, $n-1);
}
return $arr;
}
// 調用測試
$arr = [3,1,13,5,7,11,2,4,14,9,150,6,12,10,8];
print_r(heapSort($arr));
```
* * * * *
### 平均時間復雜度：O(n2)
堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
平均性能 ：O(n * logn)
其他性能 ：由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。
* * * * *
### 小結
我們知道堆的結構是節點i的孩子為2*i和2*i+1節點，大頂堆要求父節點大于等于其2個子節點，小頂堆要求父節點小于等于其2個子節點。在一個長為n 的序列，堆排序的過程是從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n /2-1, n/2-2, ...1這些個父節點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把后面一個元素交換過去了，而第n/2-1個父節點把后面一個相同的元素沒 有交換，那么這2個相同的元素之間的穩定性就被破壞了。所以，堆排序不是穩定的排序算法。
