PHP数据结构(二十四)——堆排序
(原创内容,转载请注明来源,谢谢)
一、定义
堆排序也属于一种选择排序,效率较高且空间占用相对较少。
堆的定义:n个元素的序列(k1,k2…kn),当且仅当满足以下1或者2的其中一种关系时,称为堆。
1)大顶堆:ki<=k2i且,ki<=k2i+1,其中i=1,2…n/2
2)小顶堆:ki>=k2i且,ki>=k2i+1,其中i=1,2…n/2
可将堆对应的一维数组看成一个完全二叉树,且满足非终端节点对应的值不大于(或不小于)其左右子节点的值。堆顶元素(即完全二叉树的根)必定是这个序列的最小值。(有些地方将满足此条件的完全二叉树称为二叉堆)
堆排序定义:输出堆顶元素后,用剩余的n-1个元素重组成一个堆,得到次小值。如此反复直至获取整个数组。
堆排序相比于树形排序,节约很多空间,只需要一个记录大小的辅助空间,每个待排序的记录仅占用一个空间。
二、堆的操作:
1、插入
堆的插入总是在最后一个位置,因此,插入之前的堆总是满足二叉堆的要求。
由于是用一维数组表示,即插入在一维数组的最后一个位置。然后根据节点下标,奇数是左节点,偶数是右节点,通过公式【父节点编号=(左节点编号-1)/2,或父节点编号=右节点编号/2-1】,找到其父节点的下标。
并且比较其父节点的值,如果不符合排列顺序,则交互。父节点继续往上,直至比到根节点。
2、删除
堆的删除总是删除第一个节点,即数组的第一个元素。再将数组最后一个元素放到第一个元素。接着再根据下标找到左右子节点,并且进行位置的调整。
三、堆的图与存储如下图所示(图片来自网络)
四、算法
1)将获取到的一组数组,逐个节点插入到空的一维数组(二叉堆)中,如果有必要则进行位置的调整。插入完成后,获得一个二叉堆,并且第一个元素即为最小值。
2)把第一个元素赋值给新的数组(结果数组,采用push方式赋值)后,删除第一个元素(根据定义同时将最后一个元素调整到第一个元素,其实也可以理解为把最后一个元素的值赋给第一个元素,再删除最后一个元素),再将新的根节点逐级往下进行位置的调整,获取到一个新的二叉堆。
3)重复步骤2,直至二叉堆为空。则结果数组即为排序好的数组。
五、代码主要流程:
1)根据输入的数组,采用逐个插入的方式,生成二叉堆(一维数组)。
2)将二叉堆的第一个元素取走,再将最后一个元素的值赋给第一个元素,再删除最后一个元素。
3)更新二叉堆,从根节点开始和左右子节点比较,如果有小的值则互换,互换后继续与之后的左右字节的进行比较。如果到某一层不需要互换了,则可以退出循环,不用继续往后查看互换问题。另外要注意不要超出数组下标。
4)重复2、3步骤,直到二叉堆为空,则已经获取整个数组。
六、源代码如下
//堆排序
publicfunction heapSelectSort(array $arr = array()){
$arr= $this->_checkNeedSort($arr);
if(!$arr){
return$arr;
}
//长度只有1直接返回
if(1== count($arr)){
return$arr;
}
//构造二叉堆
$heapArr= $this->_getHeapArray($arr);
//定义一个结果集
$arrRes= array();
//循环删除二叉堆
while(0< count($heapArr)){
//堆顶入结果集
array_push($arrRes,$heapArr[0]);
//堆最后一个元素赋值给第一个元素,并删除最后一个元素
//注:$heapArr[0]= array_pop($heapArr);将返回异常结果
$heapArr[0]= $heapArr[count($heapArr)-1];
array_pop($heapArr);
//unset($heapArr[count($heapArr)-1]);//array_pop也可以用这个代替
//重新调整堆顶
$heapArr= $this->_adjustHeapArray($heapArr);
}
return$arrRes;
}
//根据一维数组构造二叉堆
privatefunction _getHeapArray(array $arr = array()){
if(empty($arr)){
return$arr;
}
$heapArr= array();
$arrLength= count($arr);
for($i=0;$i<$arrLength;$i++){
$heapArr[$i]= $arr[$i];
//当前下标
$curIndex= $i;
//判断是否有必要继续循环(当插入的节点不需要互换,则后面的父节点也不用继续查询)
$needLoop= true;
while(0< $curIndex && $needLoop){
$needLoop= false;//默认不需要循环
//如果是偶数,说明是右节点,父节点是i/2-1,即与父节点比较大小,不对则互换
if(0== $curIndex%2){
if($heapArr[$curIndex]< $heapArr[$curIndex/2-1]){
$tmp= $heapArr[$curIndex];
$heapArr[$curIndex]= $heapArr[$curIndex/2-1];
$heapArr[$curIndex/2-1]= $tmp;
$curIndex= $curIndex / 2 - 1;//寻找下个父节点
$needLoop= true;//置为需要循环
}
}else{
//如果是奇数,说明是左节点,父节点是(i-1)/2,即与父节点比较大小,不对则互换
if($heapArr[$curIndex]< $heapArr[($curIndex-1)/2]){
$tmp= $heapArr[$curIndex];
$heapArr[$curIndex]= $heapArr[($curIndex-1)/2];
$heapArr[($curIndex-1)/2]= $tmp;
$curIndex= ($curIndex - 1) / 2;
$needLoop= true;//置为需要循环
}
}
}
}
return$heapArr;
}
//更新二叉堆
privatefunction _adjustHeapArray(array $heapArr = array()){
if(empty($heapArr)){
return$heapArr;
}
$curIndex= 0;//当前下标是0,开始互换
$heapNum= count($heapArr);//二叉堆的最大值
while(1){
//左子节点下标
$leftIndex= 2 * $curIndex + 1;
//左节点最大下标heapNum-1,大于此值,说明该节点没有子节点,退出循环
if($leftIndex>= $heapNum){
break;
}
//左子节点值
$leftVal= $heapArr[$leftIndex];
//右节点下标
$rightIndex= $leftIndex + 1;
//如果存在右节点值则取值,否则设置为inf
$rightVal= $rightIndex < $heapNum ? $heapArr[$rightIndex] : INF;
//比较父节点与两个子节点的大小,视情况进行互换
//先比较两个子节点,确定最小值
$childMin= $leftVal < $rightVal ? $leftVal : $rightVal;
//当前值
$curVal= $heapArr[$curIndex];
//如果父节点小于最小值,则没必要后面的比较,直接退出循环
if($curVal<= $childMin){
break;
}
//没有退出循环,说明需要进行节点互换,根据值找下标
$indexMin= $childMin == $leftVal ? $leftIndex : $rightIndex;
//互换
$heapArr[$curIndex]= $childMin;
$heapArr[$indexMin]= $curVal;
//将当前节点变为其子节点
$curIndex= $indexMin;
}
return$heapArr;
}
——written by linhxx 2017.07.20
相关阅读: