堆排序，php实现

<?php
/**
 * Created by PhpStorm.
 * User: fql
 * Date: 19/8/29
 * Time: 下午10:11
 */

namespace app\index\controller;


use think\Controller;

/**
 * Class HeapSort
 * @package app\index\controller
 * 堆排序
 */

class HeapSort extends  Controller
{

    public function  sort(){
        $arr = [1,5,4,9,6,5,7,8];
        $len =count($arr);
        for($i =$len ;$i>0;$i--){
            $this->buildHeap($arr,$i);
        }
        print_r($arr);
    }



    public function  buildHeap(&$arr,$total){
        //最后一个父节点
        $lastParentIndex = intval($total/2)-1;//最后一个父节点的位置

        for ($lastParentIndex;$lastParentIndex>=0;$lastParentIndex--){
            //左节点
            $left = $lastParentIndex*2+1;
            $right = $lastParentIndex*2+2;
            $this->swap($arr[$lastParentIndex],$arr[$left]);
            if($right<($total-1)){
                $this->swap($arr[$lastParentIndex],$arr[$right]);
                $this->swap($arr[$left],$arr[$right]);
            }
        }
        $tmp = $arr[0];
        $arr[0] = $arr[$total-1];
        $arr[$total-1] = $tmp;
    }


    public function  swap(&$min,&$max){
        if($min>$max){
            $tmp = $min;
            $min = $max;
            $max = $tmp;
        }
    }
}