堆排序

参考文章：图解排序算法(三)之堆排序

说在前面：本来对堆这种数据结构不了解，然后直接看的堆排序的介绍，看完之后一脸懵逼。。。这个堆是咋构建的？这个 “i*2+1” 是什么玩意？？？于是重新查找，终于看到了参考文章，里面详细又清楚的介绍了堆，以及堆排序，非常容易理解，也非常感谢这哥们儿，所以我一定要贴出他的这篇文章。如果看我写的还是不能理解，相信我，去看看他的那篇文章，你一定会有收获。

一、几个重要概念

1. 二叉树： 是每个结点最多有两个子树的树结构。
2. 完全二叉树：是除最后一层外，其余层都是满的，或最后一层或者是满的，或者是在右边缺少连续若干节点的二叉树。
3. 堆：是具有以下性质的完全二叉树，
   ① 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
   ② 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
   如图所示：

如果，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
假设某个节点下标为i，节点值为arr[i]，则这个节点的左子节点为arr[2i+1]，又子节点为arr[2i+2]，那么
大顶堆中满足条件：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆中满足条件：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

二、堆排序思想

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

三、算法描述

• 1.由输入的无序数组构造一个最大堆，作为初始的无序区
• 2.把堆顶元素（最大值）和堆尾元素互换
• 3.把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
• 4.重复步骤2，直到堆的尺寸为1

四、代码实现

<?php
//输出数组
function echo_arr($arr, $sym=' '){
    echo implode($sym, $arr).'<br>';
}

//交换数字
function swap_item($arr, $i, $j){
    $tmp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $tmp;
    return $arr;
}

//检测数组
function check_arr($arr){
    if(!is_array($arr)){
        return 'arr error';
    }

    $len = count($arr);
    if($len <= 1){
        return $arr;
    }

    return true;
}

//计算耗时
function time_consuming($start, $end, $name=''){
    $t = $end - $start;
    var_dump($name.'耗时：'.$t);
}

//显示起始时间
function show_time($start, $end, $name=''){
    var_dump($name.' start：'.$start);
    var_dump($name.' end  ：'.$end);
}

//获取乱序的数组
function get_test_arr($len = 200){
    for( $i = 0; $i < $len; $i++ ){
      $arr[] = mt_rand( 1,1000);
    }

    return $arr;
}

//获取顺序的数组
function get_sort_arr($len = 200){
    for( $i = 0; $i < $len; $i++ ){
      $arr[] = $i;
    }

    return $arr;
}

//排序主程序
function sort_main($arr){
    $check_re = check_arr($arr);

    if($check_re === true){
        $start = microtime(true);
        heap_sort($arr);
        $end = microtime(true);
        time_consuming($start, $end, 'quick_sort');
    }else{
        echo 'error';
        var_dump($arr);
    }
}


// $arr = array( 6, 4, 7, 2, 9, 8, 1 );
// $arr = [ 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7 ];
// $arr = [];
// $arr = '123';

$arr = get_test_arr();
// $arr = get_sort_arr();
echo_arr($arr);
// var_dump($arr);
sort_main($arr);


//堆排序
function heap_sort($arr){
    $len = count($arr);
    //1.构建大顶堆
    for ($i= $len>>2-1; $i >= 0; $i--) { 
        //从第一个非叶子结点从下至上，从右至左调整结构
        $arr = adjust_heap($arr, $i, $len);
    }
    //2.调整堆结构+交换堆顶元素与末尾元素
    for ($j=$len - 1; $j > 0; $j--) {
        //将堆顶元素与末尾元素进行交换 
        $arr = swap_item($arr, 0, $j);
        //重新对堆进行调整
        $arr = adjust_heap($arr, 0, $j);
    }
    echo_arr($arr);
}

//调整堆
function adjust_heap($arr, $cur, $len){
    //获取当前节点
    $tmp = $arr[$cur];
    //从当前节点的左子节点开始
    for ($i = $cur*2+1; $i < $len; $i = $i*2+1) { 
        //如果左子结点小于右子结点，i指向右子结点
        if($i+1 < $len && $arr[$i] < $arr[$i+1]){
            $i++;
        }
        //如果子节点大于当前节点，将子节点值赋给当前节点（不用进行交换！！！）
        if($arr[$i] > $tmp){
            $arr[$cur] = $arr[$i];
            $cur = $i;
        }else{
            break;
        }
    }
    $arr[$cur] = $tmp;

    return $arr;
}

//错误的堆调整方法
function error_adjust_heap($arr, $cur, $len){
    $tmp = $arr[$cur];
    for ($i = $cur*2+1; $i < $len; $i = $i*2+1) { 
        if($i+1 < $len && $arr[$i] < $arr[$i+1]){
            $i++;
        }
        if($arr[$i] > $tmp){
            $arr = swap_item($arr, $cur, $i);
        }else{
            break;
        }
    }

    return $arr;
}