堆
堆(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 p 2](其父子结点值的法则性);
才使患上其进行排序十分不便。
堆排序
堆排序求升序用年夜顶堆,求降序用小顶堆。
本例用求降序的小顶堆来解析。
堆排序步骤以下:
一、咱们将数据(4九、3八、6五、9七、7六、1三、2七、50)建设一个数组$arr;
二、用数组$arr建设一个小顶堆(次要步骤,会正在代码正文里诠释,下图是用一个数组建设小顶堆的进程);
三、将堆的根(最小的元素)与最初一个叶子替换,并将堆长度减一,跳到第二步;
四、反复2-3步,直到堆中只有一个结点,排序实现。
堆排序的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; }
上面是排序的终极后果:
堆用来进行全排序,工夫复杂度是O(nlogn)
而快排用来全排序,均匀工夫复杂度也是O(nlogn)
但堆排序能够用来求 TopK 时,堆的工夫复杂度为O(Klog2(n),由于它只要要进行 K 轮排序便可。
保举教程:《PHP》
以上就是基于PHP完成堆排序原理的具体内容,更多请存眷资源魔其它相干文章!
标签: php 实现 php开发教程 php开发资料 php开发自学 堆排序
抱歉,评论功能暂时关闭!