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 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

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

PHP数据结构(二十)——其他插入排序 (原创内容,转载请注明来源,谢谢) 注:本文是衔接直接插入排序的,因此直接插入排序的相关内容请点击——PHP...

3107
来自专栏决胜机器学习

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

PHP数据结构(八)——赫夫曼树实现字符串编解码(理论) (原创内容,转载请注明来源,谢谢) 一、树和森林 1、树的三种存储结构 1)双亲表示法——数组下标、值...

3349
来自专栏AzMark

Python 学习之元组列表

774
来自专栏猿人谷

总结---2

1.各种排序算法的时间复杂度和空间复杂度分析 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。...

1618
来自专栏吴伟祥

认识XPath(确定XML文档中某部分位置的语言)

XPath即为XML路径语言(XML Path Language),它是一种用来确定XML文档中某部分位置的语言。

381
来自专栏小樱的经验随笔

HUST 1586 数字排列

1586 - 数字排列 时间限制:1秒 内存限制:128兆 91 次提交 36 次通过 题目描述现有n个k位的数字,你的任务是重新安排数字每一位的位置,使得...

26212
来自专栏书山有路勤为径

逆序数(二叉查找树)

已知数组nums,求新数组count,count[i]代表了在nums[i]右侧且比nums[i]小的元素个数。 例如: nums = [5,2,6,1],...

513
来自专栏王硕

原 B树C语言代码实现

3759
来自专栏ml

C plus plus 控制格式

使用这些格式需要声明包含<iomainip> long flags( ) const 返回当前的格式标志。 long flays(long newflag) 设...

2054
来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

1756

扫描关注云+社区