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

相关阅读:

PHP数据结构(二十三) ——快速排序

PHP数据结构(二十二) ——快速排序

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十) ——其他插入排序

PHP数据结构(十九) ——B+树

PHP数据结构(十八) ——直接插入排序

PHP数据结构(十七) ——内部排序综述

PHP数据结构(十六) ——B树

PHP数据结构(十五) ——哈希表​

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1786
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1272
来自专栏CodingToDie

Awesome 项目

3385
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

771
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5886
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2478
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

2631
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2169
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3729

扫码关注云+社区