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

相关文章

来自专栏柠檬先生

Sass 基础(六)

join() 函数    join()函数是将两个列表连接合并成一个列表。    >>join(10px 20px, 30px 40px)       (...

19210
来自专栏有趣的Python

慕课网-c语言入门-学习笔记

个人整理,学习自用。课程内容by慕课网。 c语言入门 C语言一经出现就以其功能丰富、表达能力强、灵活方便、应用面广等特点迅速在全世界普及和推广。C语言不但执行效...

4226
来自专栏禅林阆苑

mysql学习总结02 — 数据类型

无符号:表示存储的数据在当前字段中,没有负数(只有正数,例如 tinyint 区间为 0~255)

1122
来自专栏腾讯数据库技术

听原作者为你深度解读InnoDB批量建索引原理

1843
来自专栏ml

排序

排序法 平均时间 最差情形 稳定度 额外空间 冒泡 O(n2)     O(n2) 稳定 O(1) 交换     O(n2)     O(n2) ...

3085
来自专栏C/C++基础

printf()详解之终极无惑

printf()是C语言标准库函数,用于将格式化后的字符串输出到标准输出。标准输出,即标准输出文件,对应终端的屏幕。printf()申明于头文件stdio.h。

1773
来自专栏数据结构与算法

洛谷P3380 【模板】二逼平衡树(树套树)

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

2083
来自专栏专注 Java 基础分享

堆结构的优秀实现类----PriorityQueue优先队列

     之前的文章中,我们有介绍过动态数组ArrayList,双向队列LinkedList,键值对集合HashMap,树集TreeMap。他们都各自有各自的优...

2106
来自专栏恰同学骚年

数据结构基础温故-7.排序

排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

661
来自专栏MasiMaro 的技术博文

地址、指针与引用

计算机本身是不认识程序中给的变量名,不管我们以何种方式给变量命名,最终都会转化为相应的地址,编译器会生成一些符号常量并且与对应的地址相关联,以达到访问变量的目的...

661

扫码关注云+社区