PHP数据结构（二十四） ——堆排序
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
相关阅读：