堆排序：是一种特殊形式的选择排序，他是简单选择排序的一种改进。
什么是堆？
具有n个元素的序列：{k1,k2,ki,…,kn}
(ki <= k2i,ki <= k2i+1) 或者 (ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
满足这个条件时，该序列就是一个堆。第一个条件称为小顶堆，第二个条件称为大顶堆。
为了方便，下边论述基于大顶堆，并且下标从1开始。
将堆的元素放在一棵完全二叉树中，方便我们讨论堆的特性和排序，一般谈到堆也都是一棵完全二叉树。
完全二叉树：若二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
堆的特性（括号道标下标从0开始的计算方法） ：
- 非叶子结点个数：n / 2 （n / 2 - 1）
- 节点i的左子树下标 ：2*i （2*i+ 1）
- 节点i的右子树下标：2*i + 1 （2*i + 2）
堆排序：
核心思想：
- 将原始序列构成一个堆。（建立初始堆）
- 交换堆的第一个元素（最大值）和最后一个元素的位置，把堆长度减一后剩余的序列再转换为一个堆。（调整堆）
- 重复2过程n-1次。
经过上述操作，就可以将一个无序序列从小到大排序。（因为大顶堆每次把最大值交换到最后了,所以想要降序排列就要用小顶堆）
先说调堆，调堆就是把当前节点和其左子树，右子树中最大值交换，依次把需要调整的节点调一遍。这样一次循环下来根节点肯定放的是最大值。但是有可能循环中的某次交换把之前排好序的结构打乱，需要递归调整。
再说建堆，建堆就是从最后一个非叶子节点开始，到第一个节点为止，依次进行调堆。
for ($i = floor(count($arr) / 2) - 1; $i >=0; $i--) {
adjustHeap($arr);
}
借用网上的一张图说明一下：
从floor（9/2）-1开始，也就是key=3，val=5的地方开始，循环调堆，到图1.6处循环完成，最大值顺利到达根节点，但是发现val=1节点还是需要调整，这就需要在调堆里执行循环调整，使其符合堆的特性。
代码实现：
$arr = [49, 38, 65, 97, 76, 13, 27, 50];
sortHeap($arr);
print_r($arr);
function sortHeap(&$arr)
{
//先建堆
buildHeap($arr);
//把第一个节点和最后一个节点交换,直到节点数为1
$count = count($arr);
while ($count > 1) {
swap($arr, $count - 1, 0); //交换第一个和最后一个元素
$count--; //去掉最后一个元素后剩余元素再进行调整
adjustHeap($arr, $count, 0);
}
}
function buildHeap(&$arr)
{
$node = floor(count($arr) / 2) - 1; //非叶子节点的最大节点,下标从0开始
for ($i = $node; $i >= 0; $i--) { //从最大非叶子节点循环调整每个节点
adjustHeap($arr, count($arr), $i);
}
}
//调整堆,接受maxLen为当前堆需要调整的元素最大值，node为当前要调整的节点
function adjustHeap(&$arr, $maxLen, $node)
{
$lchild = 2 * $node + 1; //左子树
$rchild = 2 * $node + 2; //右子树
$max = $node; //设置当前节点为最大值的节点,方便后边最大值节点变化时与当前节点比较,确认是否需要交换
while ($lchild < $maxLen || $rchild < $maxLen) { //左子树和右子树任一个符合条件就进入循环
if ($lchild < $maxLen && $arr[$lchild] > $arr[$max]) { //左子树大于当前节点值得话设置设置$max
$max = $lchild;
}
if ($rchild < $maxLen && $arr[$rchild] > $arr[$max]) {
$max = $rchild;
}
if ($max != $node) {
swap($arr, $max, $node);
$node = $max; //把当前节点切换为最大值的那个节点,迭代使其符合堆特性
$lchild = 2 * $node + 1;
$rchild = 2 * $node + 2;
} else {
break; //没有发生交换就退出
}
}
}
function swap(&$arr, $m, $n)
{
$arr[$m] = $arr[$m] ^ $arr[$n];
$arr[$n] = $arr[$n] ^ $arr[$m];
$arr[$m] = $arr[$m] ^ $arr[$n];
}