堆排序是排序算法中的一种，时间复杂度是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);
