PHP回顾--堆排序
2019-04-12| 程成| 22| 0| PHP技术
标签:PHP排序

一、定义


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



二、排序演示


给定一个列表array=[16,7,3,20,17,8],对其进行堆排序。

首先根据该数组元素构建一个完全二叉树,得到


image.png


然后需要构造初始堆,则从最后一个非叶节点开始调整,调整过程如下:

第一步: 初始化大顶堆(从最后一个有子节点开始往上调整最大堆)


image.png



20和16交换后导致16不满足堆的性质,因此需重新调整


image.png


这样就得到了初始堆。


第二步: 堆顶元素R[1]与最后一个元素R[n]交换,交换后堆长度减一

即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。



image.png


第三步: 重新调整堆。此时3位于堆顶不满堆的性质,则需调整继续调整(从顶点开始往下调整)


image.png


重复上面的步骤:


image.png


注意了,现在你应该了解堆排序的思想了,给你一串列表,你也能写出&说出堆排序的过程。


在写算法的过程中,刚开始我是很懵比。后来终于看懂了。请特别特别注意: 初始化大顶堆时 是从最后一个有子节点开始往上调整最大堆。而堆顶元素(最大数)与堆最后一个数交换后,需再次调整成大顶堆,此时是从上往下调整的。


不管是初始大顶堆的从下往上调整,还是堆顶堆尾元素交换,每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换,交换之后都可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整。我在算法中是用一个while循环来解决的





三、性能分析


堆排序是对直接选择排序的改进算法,选择排序的特点在于每次选取最小或最大的值,而选取最大值时的比较次数为复杂度的关键,堆排序采用二叉树的方法存储元素,每个节点都满足父节点的值大于等于子节点的特点,与直接选择排序类似,堆排序需要两个个值的空间来存储临时变量,用于交换节点,一次用于存储子树最大节点用于交换子节点,一次用于存储堆顶的值用于交换最后的节点,所以空间复杂度为O(1)。


采用堆的方式寻找最大值是降低时间复杂度的关键,假设有n个数据,需要n-1次建堆的过程,每次建堆的时间复杂度为log2n,但是无论序列的开始状态如何,都需要对堆进行遍历寻找最大值,所以在最好情况、最坏情况和平均情况下的时间复杂度都是O(nlog2n)。


稳定性 

堆排序是利用堆的特点,堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是一个稳定的排序算法。



四、代码实现


<?php
//堆排序(对简单选择排序的改进)
function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}


//调整 $arr[$start]的关键字,使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆(根节点最大的完全二叉树)
//注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 (数组开始下标为 0 时)
function HeapAdjust(array &$arr,$start,$end){
    $temp = $arr[$start];
    //沿关键字较大的孩子节点向下筛选
    //左右孩子计算(我这里数组开始下标识 0)
    //左孩子2 * $start + 1,右孩子2 * $start + 2
    for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
        if($j != $end && $arr[$j] < $arr[$j + 1]){
            $j ++; //转化为右孩子
        }
        if($temp >= $arr[$j]){
            break;  //已经满足大根堆
        }
        //将根节点设置为子节点的较大值
        $arr[$start] = $arr[$j];
        //继续往下
        $start = $j;
    }
    $arr[$start] = $temp;
}


function HeapSort(array &$arr){
    $count = count($arr);
    //先将数组构造成大根堆(由于是完全二叉树,所以这里用floor($count/2)-1,下标小于或等于这数的节点都是有孩子的节点)
    for($i = floor($count / 2) - 1;$i >= 0;$i --){
        HeapAdjust($arr,$i,$count);
    }
    for($i = $count - 1;$i >= 0;$i --){
        //将堆顶元素与最后一个元素交换,获取到最大元素(交换后的最后一个元素),将最大元素放到数组末尾
        swap($arr,0,$i);  
        //经过交换,将最后一个元素(最大元素)脱离大根堆,并将未经排序的新树($arr[0...$i-1])重新调整为大根堆
        HeapAdjust($arr,0,$i - 1);
    }
}

$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);



参考文献:https://www.cnblogs.com/0zcl/p/6737944.html





×
作者:程成
QQ:492245711