用PHP怎样实现堆排序?其原理你知道吗?
发布时间:2021-12-23 16:54:36 所属栏目:PHP教程 来源:互联网
导读:用PHP怎样实现堆排序?要解决这个问题,首先我们需要了解关于堆,完成二叉树以及堆排序的原理,本文后面有堆排序的PHP实现代码,有需要的朋友可以参考一下。 堆 堆(heap)是计算机科学中一类特殊的数据结构的统称,通常是一个可以被看做一棵树的数组对象。堆{
用PHP怎样实现堆排序?要解决这个问题,首先我们需要了解关于堆,完成二叉树以及堆排序的原理,本文后面有堆排序的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实现 //因为是数组,下标从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); } (编辑:常州站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |