10大经典排序算法之堆排序(PHP版)

发布时间:2020/11/20 作者:天马行空 阅读(166)

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


算法步骤
1、对原数组构建成大(小)顶堆,顶部就是最(小)值;
2、交换头尾值,最后一个值就是最大值,固定最(小)值;
3、然后索引减1,将最后一个值排除在外,用剩下的值继续构建大顶堆;
4、重复1-3步骤,直到堆中只剩一个,倒序的数组就出来了。


动图演示

heapSort.gif


代码实现:

public function heapSort($arr)
{
    $len = count($arr);
    
    // 完全二叉树有一个性质:最后一个非叶结点是第n/2个结点。
    for ($i = floor($len / 2); $i >= 0; $i --) {
        $this->heapify($arr, $i, $len);
    }
    
    for ($i = count($arr) - 1; $i > 0; $i --) {
        $this->swap($arr, 0, $i);
        $len --;
        $this->heapify($arr, 0, $len); // 新的二叉树从上往下替换
    }
    return $arr;
}

/**
 * 找出节点下的最大值
 * 
 * @param array $arr   要排序的数组
 * @param int   $i     从什么位置开始找最大值
 * @param int   $len   堆的长度
 */
private function heapify(&$arr, $i, $len)
{
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;
    $largest = $i; // 默认节点就是最大值
    
    if ($left < $len && $arr[$left] > $arr[$largest]) { // 左叶子节点比最大值大,最大值就是左叶子节点
        $largest = $left;
    }
    
    if ($right < $len && $arr[$right] > $arr[$largest]) { // 右叶子节点比最大值大,最大值就是右叶子节点
        $largest = $right;
    }
    
    if ($largest != $i) {
        $this->swap($arr, $i, $largest);
        $this->heapify($arr, $largest, $len); // 从最大的节点位置往下继续替换,将小的值扔到子节点上去
    }
}

//交换位置
private function swap(&$arr, $i, $j)
{
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}



关键字php 算法