参考文章：图解排序算法(三)之堆排序
说在前面：本来对堆这种数据结构不了解，然后直接看的堆排序的介绍，看完之后一脸懵逼。。。这个堆是咋构建的？这个 “i*2+1” 是什么玩意？？？于是重新查找，终于看到了参考文章，里面详细又清楚的介绍了堆，以及堆排序，非常容易理解，也非常感谢这哥们儿，所以我一定要贴出他的这篇文章。如果看我写的还是不能理解，相信我，去看看他的那篇文章，你一定会有收获。
一、几个重要概念
- 二叉树： 是每个结点最多有两个子树的树结构。
- 完全二叉树：是除最后一层外，其余层都是满的，或最后一层或者是满的，或者是在右边缺少连续若干节点的二叉树。
- 堆：是具有以下性质的完全二叉树，
① 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
② 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
如图所示：如果，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
假设某个节点下标为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;
}
