### 基本原理
利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即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个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
