堆排序

---

堆排序(Heap Sort)

堆排序是指利用堆这种数据结构所设计的一种排序算法。 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质； 即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述

• 将初始等排序关键字序列(R1,R2...Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2...Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2...Rn-2)和新的有序区(Rn-1,Rn)。 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

个人理解

先建立一个最小堆，则最小值入堆顶。父结点比左节点小，左节点比右节点小。 将堆顶放到堆尾。

动图演示

代码实现

//因为是数组,下标从0开始,所以,下标为n根结点的左子结点为2n+1,右子结点为2n+2;
//初始化值,建立初始堆
$arr=array(49,38,65,97,76,13,27,50);
$arrSize=count($arr);

//将第一次排序抽出来，因为最后一次排序不需要再交换值了。
buildHeap($arr,$arrSize);

for($i=$arrSize-1;$i>0;$i--){
    swap($arr,$i,0);
    $arrSize--;
    buildHeap($arr,$arrSize);
}

//用数组建立最小堆
function buildHeap(&$arr,$arrSize){
    //计算出最开始的下标$index,如图,为数字"97"所在位置,比较每一个子树的父结点和子结点,将最小值存入父结点中
    //从$index处对一个树进行循环比较,形成最小堆
    for($index=intval($arrSize/2)-1; $index>=0; $index--){
        //如果有左节点,将其下标存进最小值$min
        if($index*2+1<$arrSize){
            $min=$index*2+1;
            //如果有右子结点,比较左右结点的大小,如果右子结点更小,将其结点的下标记录进最小值$min
            if($index*2+2<$arrSize){
                if($arr[$index*2+2]<$arr[$min]){
                    $min=$index*2+2;
                }
            }
            //将子结点中较小的和父结点比较,若子结点较小,与父结点交换位置,同时更新较小
            if($arr[$min]<$arr[$index]){
                swap($arr,$min,$index);
            }
        }
    }
}

//此函数用来交换下数组$arr中下标为$one和$another的数据
function swap(&$arr,$one,$another){
    $tmp=$arr[$one];
    $arr[$one]=$arr[$another];
    $arr[$another]=$tmp;
}

var_dump($arr);

$arr = [20, 40, 60, 80, 30, 70, 90, 10, 50, 0, 5];

/**
 * @param $arr
 * 堆排序
 */
function heapSort(&$arr)
{
    $arrSize = count($arr); // 取数据长度
    // 建最小堆，依次入堆尾
    for ($i = $arrSize - 1; $i > 0; $i--) {
        buildMinHeap($arr, $arrSize); // 建最小堆
        $arrSize--;
        swap($arr, $i, 0); // 入堆尾
    }
}

/**
 * @param $arr
 * @param $arrSize
 * 最小堆
 */
function buildMinHeap(&$arr, $arrSize)
{
    $index = floor($arrSize / 2) - 1; // 顶点(最尾)

    for (; $index >= 0; $index--) {
        $left = $index * 2 + 1; // 左节点
        $right = $index * 2 + 2; // 右节点

        if ($left < $arrSize) $min = $left; // 左节点入哨兵
        if ($right < $arrSize && $arr[$right] < $arr[$min]) $min = $right; // 右节点入哨兵
        if ($arr[$min] < $arr[$index]) swap($arr, $min, $index); // 将小值入顶点
    }
}

/**
 * @param $arr
 * @param $min
 * @param $index
 * 数据交换
 */
function swap(&$arr, $min, $index)
{
    $tmp = $arr[$min];
    $arr[$min] = $arr[$index];
    $arr[$index] = $tmp;
}

heapSort($arr);
var_dump($arr);