堆排序

堆排序是利用二叉堆的自调整特性将数组变为有序序列的排序方法
二叉堆的特性：

1. 最大堆的堆顶是整个堆中的最大元素。
2. 最小堆的堆顶是整个堆中的最小元素。

堆排序算法的步骤：

1. 把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
2. 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。

具体代码如下：
此代码二叉堆的构建有些问题，输出的并不是一个最大堆，有时间再思考下，先将代码贴出

class Code{
    
    /**
    * “下沉”调整 自上而下比较父节点和子节点
    * @param array 待调整的堆
    * @param parentIndex 要“下沉”的父节点
    * @param length 堆的有效大小
    */
    function downAdjust(&$arr,$parentIndex,$length){
        // tmp 保存父节点值，用于最后的赋值
        $tmp = $arr[$parentIndex];
        $childIndex = $parentIndex*2 + 1;
        while ($childIndex < $length) {
            // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
            if($childIndex+1 < $length && $arr[$childIndex] < $arr[$childIndex+1]){
                $childIndex++;
            }
            // 如果父节点大于任何一个孩子的值，则直接跳出
            if($tmp >= $arr[$childIndex]){
                break;
            }
            //无须真正交换，单向赋值即可
            $arr[$parentIndex] = $arr[$childIndex];
            //下移父节点和子节点，继续对比调整
            $parentIndex = $childIndex;
            $childIndex = $parentIndex*2 + 1;
        }
        $arr[$parentIndex] = $tmp;
    }

    /**
    * 堆排序（升序）
    * @param arr 待调整的堆
    */
    function heapSort(&$arr){
        $intLength = count($arr);
        //1.把无序数组构建为最大堆
        for ($i=($intLength-2)/2; $i >= 0; $i--) { 
            $this->downAdjust($arr,$i,$intLength);
        }
        //2.循环删除堆顶，移动到堆的尾部，调整堆产生新的堆顶
        for ($i=$intLength-1; $i > 0; $i--) { 
            //最后一个元素与第一个元素交换位置
            $tmp = $arr[$i];
            $arr[$i] = $arr[0];
            $arr[0] = $tmp;
            //下沉调整最大堆
            $this->downAdjust($arr,0,$i);
        }
    }



    //运行
    function run(){
        $arr = array(8,5,7,4,2,0,1,3,9);
        $this->heapSort($arr);
        print_r($arr);
    }
    
}
$obj = new Code();
$obj->run();

空间复杂度是O(1)，因为并没有开辟额外的集合空间
时间复杂度的计算
堆排序算法的步骤。

1. 把无序数组构建成二叉堆。
2. 循环删除堆顶元素，并将该元素移到集合尾部，调整堆产生新的堆顶。
   第1步，把无序数组构建成二叉堆，这一步的时间复杂度是O(n)。
   第2步，需要进行n-1次循环。每次循环调用一次downAdjust方法，所以第2步的计算规模是 (n-1)×logn ，时间复杂度为O(nlogn)。