欢迎来到站长教程网!

PHP教程

当前位置:主页 > 网络编程 > PHP教程 >

基于PHP实现堆排序原理及实例详解

时间:2020-06-19|栏目:PHP教程|点击:

堆(heap)是计算机科学中一类特殊的数据结构的统称,通常是一个可以被看做一棵树的数组对象。

堆{k1,k2,ki,…,kn} (ki <= k2i,ki <= k2i+1)|(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

关于堆:

堆中某个节点的值总是不大于或不小于其父节点的值;

堆总是一棵完全二叉树(下面)。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

完全二叉树

说到堆排序,就不能不提完全二叉树,这些基本概念在网上到处都是,我摘了个最简单的。。

完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。

我自己总结认为,正是因为有下面两个特点,

只允许最后一层有空缺结点且空缺在右边,即叶子结点只能在层次最大的两层上出现(存储方式的规则性);

若i>1,tree的双亲为tree[i div 2](其父子结点值的规律性);

才使得其进行排序非常方便。

堆排序

堆排序求升序用大顶堆,求降序用小顶堆。

本例用求降序的小顶堆来解析。

堆排序步骤如下:

1、我们将数据(49、38、65、97、76、13、27、50)建立一个数组$arr;

2、用数组$arr建立一个小顶堆(主要步骤,会在代码注释里解释,下图是用一个数组建立小顶堆的过程);

3、将堆的根(最小的元素)与最后一个叶子交换,并将堆长度减一,跳到第二步;

4、重复2-3步,直到堆中只有一个结点,排序完成。

基于PHP实现堆排序原理及实例详解

堆排序的PHP实现

//因为是数组,下标从0开始,所以,下标为n根结点的左子结点为2n+1,右子结点为2n+2; //初始化值,建立初始堆 $arr=array(49,38,65,97,76,13,27,50); $arrSize=count($arr); //将第一次排序抽出来,因为最后一次排序不需要再交换值了。 buildHeap($arr,$arrSize); for($i=$arrSize-1;$i>0;$i--){ swap($arr,$i,0); $arrSize--; buildHeap($arr,$arrSize); } //用数组建立最小堆 function buildHeap(&$arr,$arrSize){ //计算出最开始的下标$index,如图,为数字"97"所在位置,比较每一个子树的父结点和子结点,将最小值存入父结点中 //从$index处对一个树进行循环比较,形成最小堆 for($index=intval($arrSize/2)-1; $index>=0; $index--){ //如果有左节点,将其下标存进最小值$min if($index*2+1<$arrSize){ $min=$index*2+1; //如果有右子结点,比较左右结点的大小,如果右子结点更小,将其结点的下标记录进最小值$min if($index*2+2<$arrSize){ if($arr[$index*2+2]<$arr[$min]){ $min=$index*2+2; } } //将子结点中较小的和父结点比较,若子结点较小,与父结点交换位置,同时更新较小 if($arr[$min]<$arr[$index]){ swap($arr,$min,$index); } } } } //此函数用来交换下数组$arr中下标为$one和$another的数据 function swap(&$arr,$one,$another){ $tmp=$arr[$one]; $arr[$one]=$arr[$another]; $arr[$another]=$tmp; }

下面是排序的最终结果:

基于PHP实现堆排序原理及实例详解

上一篇:如何在PHP环境中使用ProtoBuf数据格式

栏    目:PHP教程

下一篇:PHP基于openssl实现非对称加密代码实例

本文标题:基于PHP实现堆排序原理及实例详解

本文地址:http://www.blue1000.com/wangluobiancheng/PHPjiaocheng/2000.html

广告投放 | 联系我们 | 版权申明

重要申明:本站所有的文章、图片、评论等,均由网友发表或上传并维护或收集自网络,属个人行为,与本站立场无关。

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:1961407250 | 邮箱:1961407250#qq.com(#换成@)

Copyright © 2002-2022 BK网络学院版权所有 Power by DedeCms 粤ICP备19027147号-7