堆排序，是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。大顶堆升序，小顶堆降序。

算法步骤
1、对原数组构建成大（小）顶堆，顶部就是最（小）值；
2、交换头尾值，最后一个值就是最大值，固定最（小）值；
3、然后索引减1，将最后一个值排除在外，用剩下的值继续构建大顶堆；
4、重复1-3步骤，直到堆中只剩一个，倒序的数组就出来了。

动图演示

代码实现：

public function heapSort($arr)
{
    $len = count($arr);
    
    // 完全二叉树有一个性质：最后一个非叶结点是第n/2个结点。
    for ($i = floor($len / 2); $i >= 0; $i --) {
        $this->heapify($arr, $i, $len);
    }
    
    for ($i = count($arr) - 1; $i > 0; $i --) {
        $this->swap($arr, 0, $i);
        $len --;
        $this->heapify($arr, 0, $len); // 新的二叉树从上往下替换
    }
    return $arr;
}

/**
 * 找出节点下的最大值
 * 
 * @param array $arr   要排序的数组
 * @param int   $i     从什么位置开始找最大值
 * @param int   $len   堆的长度
 */
private function heapify(&$arr, $i, $len)
{
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;
    $largest = $i; // 默认节点就是最大值
    
    if ($left < $len && $arr[$left] > $arr[$largest]) { // 左叶子节点比最大值大，最大值就是左叶子节点
        $largest = $left;
    }
    
    if ($right < $len && $arr[$right] > $arr[$largest]) { // 右叶子节点比最大值大，最大值就是右叶子节点
        $largest = $right;
    }
    
    if ($largest != $i) {
        $this->swap($arr, $i, $largest);
        $this->heapify($arr, $largest, $len); // 从最大的节点位置往下继续替换，将小的值扔到子节点上去
    }
}

//交换位置
private function swap(&$arr, $i, $j)
{
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}