堆 -（堆构建及堆排序）

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

1.堆的性质：

1.堆中某个节点的值总是不大于（大顶堆）或不小于（小顶堆）其父节点的值。
2.堆总是一棵完全二叉树。

2.大顶堆构造案例：

<?php
/**
 * @Author: fql
 * @Email: fangqiulin4923@gmail.com
 * @Date: 2020-07-19 22:41
 */

namespace fql\algorithm\sort;

use fql\sort\Sort;

/**
 * Class Heap
 * @package fql\structure
 * 堆性质：1.对于任何节点，如果节点序号为i，则其左节点为2*i+1,其右节点序号为:2*i+2
 *       2.堆的最后一个非叶子节点若只有左孩子，则：2*i+1 = n-1 =>i=n/2-1
 *       3.堆的最后一个非叶子节点有左右两个孩子, 则：2*i+1 = n-2 或者  2*i+2 = n-1 =>i=(n-3)/2,向下取整，可得到：i=n/2-1
 *       4.不稳定排序，内排序
 *       5.时间复杂度：n*log(n)
 */
class HeapSort extends Sort
{
    public function sort(&$array){
        //数组长度
        $len = count($array);
        //进行n趟，每趟数组长度减少1
        for($n = $len ; $n>0; $n--){
            //最后一个非叶子节点
            $node = floor($n/2)-1;
            $this->adjust($array,$node,$n);
            //互换首尾
            $tmp = $array[0];
            $array[0] = $array[$n - 1];
            $array[$n - 1]= $tmp;
        }
        print_r($array);
    }

    /**
     * @param $array
     * @param $node
     * 调整每个节点的位置
     */
    public  function  adjust(&$array,$node,$n){
        if($node < 0){
            return $array;
        }
        $left = 2 * $node + 1;
        $right = 2 * $node + 2;
        //无右节点
        if($right >= $n){
            //父节点和左节点比较
            $this->swap($array,$node, $left);
        }else{
            //父节点和左节点比较
            $this->swap($array,$node, $left);
            //父节点和右节点比较
            $this->swap($array,$node, $right);
        }
        $node--;
        $this->adjust($array,$node,$n);

    }


    protected function swap(&$array,$i,$j){
        if($array[$i] < $array[$j]){
            $tmp = $array[$i];
            $array[$i] = $array[$j];
            $array[$j] = $tmp;
        }
    }
}