堆排序

堆排序是排序算法中的一种，时间复杂度是O(n log(n))。

堆是由完全二叉树实现的

大顶堆：父节点都比子节点要大
小顶堆：父节点都比子节点要小

子节点位置计算：C1 = 2i +1 C2 = 2i+2
父节点位置计算：parent = (i-1)/2 向下取整

实现思路：
将未排序数组处理成堆
根据堆特性建立大顶堆或者小顶堆
循环截取堆顶完成排序
参考链接：堆排序讲解

代码实现：

<?php

//位置交换
function swap(array $tree, $max, $i){
    $temp = $tree[$i];
    $tree[$i] = $tree[$max];
    $tree[$max] = $temp;

    return $tree;
}

//堆处理，大顶堆或者小顶堆
/*
 * $tree = 堆
 * $n = 总数
 * $i = 父节点位置
 */
function heapify( array $tree, int $n, int $i){
    static $last_tree = [];
    //递归出口
    if($i >= $n){
        return $tree;
    }
    //第一个子节点
    $C1 = 2 * $i + 1;
    //第二个子节点
    $C2 = 2 * $i + 2;

    $max = $i;

    if($C1 < $n && $tree[$C1] > $tree[$max]){
        $max = $C1;
    }

    if($C2 < $n && $tree[$C2] > $tree[$max]){
        $max = $C2;
    }
    //位置交换
    if($max != $i){
        $tree  = swap($tree, $max, $i);
        $last_tree = $tree;
        heapify($tree, $n, $max);
    }

    return $last_tree;
}

//生成堆
function build_heap(array $tree, int $n){
    $last_node  =  $n - 1;
    $parent = (int)($last_node -1) / 2;
    for ($i = $parent; $i >= 0; $i --) {
        $tree = heapify($tree, $n, $i);
    }
    return $tree;
}

//堆排序
function heap_sort(array $tree, int $n){
    $tree = build_heap($tree, $n);
    for ($i = $n - 1; $i >= 0; $i--){
        $tree = swap($tree, $i, 0);
        if($i > 2){
            $tree = heapify($tree, $i, 0);
        }
    }

    return $tree;
}

//未排序数组
$tree = [2,5,3,1,10,4];
$total_num = count($tree);
$tree = heap_sort($tree, $total_num);
print_r($tree);