參考文章：圖解排序算法(三)之堆排序

說在前面：本來對堆這種數(shù)據(jù)結(jié)構(gòu)不了解，然后直接看的堆排序的介紹，看完之后一臉懵逼。。。這個堆是咋構(gòu)建的？這個 “i*2+1” 是什么玩意？？？于是重新查找，終于看到了參考文章，里面詳細(xì)又清楚的介紹了堆，以及堆排序，非常容易理解，也非常感謝這哥們兒，所以我一定要貼出他的這篇文章。如果看我寫的還是不能理解，相信我，去看看他的那篇文章，你一定會有收獲。

一、幾個重要概念

1. 二叉樹： 是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)。
2. 完全二叉樹：是除最后一層外，其余層都是滿的，或最后一層或者是滿的，或者是在右邊缺少連續(xù)若干節(jié)點的二叉樹。
3. 堆：是具有以下性質(zhì)的完全二叉樹，
   ① 每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為大頂堆；
   ② 或者每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小頂堆。
   如圖所示：

如果，我們對堆中的結(jié)點按層進(jìn)行編號，將這種邏輯結(jié)構(gòu)映射到數(shù)組中就是下面這個樣子：

該數(shù)組從邏輯上講就是一個堆結(jié)構(gòu)，我們用簡單的公式來描述一下堆的定義就是：
假設(shè)某個節(jié)點下標(biāo)為i，節(jié)點值為arr[i]，則這個節(jié)點的左子節(jié)點為arr[2i+1]，又子節(jié)點為arr[2i+2]，那么
大頂堆中滿足條件：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小頂堆中滿足條件：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

二、堆排序思想

將待排序序列構(gòu)造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母?jié)點。將其與末尾元素進(jìn)行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復(fù)執(zhí)行，便能得到一個有序序列了。

三、算法描述

• 1.由輸入的無序數(shù)組構(gòu)造一個最大堆，作為初始的無序區(qū)
• 2.把堆頂元素（最大值）和堆尾元素互換
• 3.把堆（無序區(qū)）的尺寸縮小1，并調(diào)用heapify(A, 0)從新的堆頂元素開始進(jìn)行堆調(diào)整
• 4.重復(fù)步驟2，直到堆的尺寸為1

四、代碼實現(xiàn)

<?php
//輸出數(shù)組
function echo_arr($arr, $sym=' '){
    echo implode($sym, $arr).'<br>';
}

//交換數(shù)字
function swap_item($arr, $i, $j){
    $tmp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $tmp;
    return $arr;
}

//檢測數(shù)組
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);
}

//獲取亂序的數(shù)組
function get_test_arr($len = 200){
    for( $i = 0; $i < $len; $i++ ){
      $arr[] = mt_rand( 1,1000);
    }

    return $arr;
}

//獲取順序的數(shù)組
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.構(gòu)建大頂堆
    for ($i= $len>>2-1; $i >= 0; $i--) { 
        //從第一個非葉子結(jié)點從下至上，從右至左調(diào)整結(jié)構(gòu)
        $arr = adjust_heap($arr, $i, $len);
    }
    //2.調(diào)整堆結(jié)構(gòu)+交換堆頂元素與末尾元素
    for ($j=$len - 1; $j > 0; $j--) {
        //將堆頂元素與末尾元素進(jìn)行交換 
        $arr = swap_item($arr, 0, $j);
        //重新對堆進(jìn)行調(diào)整
        $arr = adjust_heap($arr, 0, $j);
    }
    echo_arr($arr);
}

//調(diào)整堆
function adjust_heap($arr, $cur, $len){
    //獲取當(dāng)前節(jié)點
    $tmp = $arr[$cur];
    //從當(dāng)前節(jié)點的左子節(jié)點開始
    for ($i = $cur*2+1; $i < $len; $i = $i*2+1) { 
        //如果左子結(jié)點小于右子結(jié)點，i指向右子結(jié)點
        if($i+1 < $len && $arr[$i] < $arr[$i+1]){
            $i++;
        }
        //如果子節(jié)點大于當(dāng)前節(jié)點，將子節(jié)點值賦給當(dāng)前節(jié)點（不用進(jìn)行交換！?。。?        if($arr[$i] > $tmp){
            $arr[$cur] = $arr[$i];
            $cur = $i;
        }else{
            break;
        }
    }
    $arr[$cur] = $tmp;

    return $arr;
}

//錯誤的堆調(diào)整方法
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;
}