PHP实现的堆排序算法详解

本文阐述了用PHP实现的堆排序算法。分享给大家参考，如下：

经验

工作之后，在为这家公司面试的时候被技术方打得很惨，因为我的数据结构基础知识真的很差，虽然我原本想做设计师。不过，鉴于PHP写得还算不错，我可以来练习，但我还是决心把基础补上。其实之前确实感受到了基础的重要性，一些更深层次的东西都在底层，不学好是做不到的。我之前用PHP做websocket的时候，涉及到数据包、数据帧等概念，不太清楚。甚至连数据都无法处理，只能以后补充。所以我要重新学习数据结构、算法、网络等基础知识。而且我想在这里提醒大家，不要像我这样反其道而行之，怕是来不及理解。

今天，我们来谈谈堆排序的问题。当时问的时候，我忘记了完全二叉树的概念。不过好在我还是有一点数据结构基础的，看了一些数据也有了一些了解，所以想用PHP写二叉树的堆排序，顺便复习一下二叉树、堆等数据结构。

大量

堆是计算机科学中一种特殊数据结构的总称，通常是一个可以看作树的数组对象。

堆{k1，k2，ki，…，kn} (ki=k2i，ki=k2i1) | (ki=k2i，ki=k2i1)，(I=1，2，3，4.n/2)

关于堆：

堆中节点的值始终不大于或不小于其父节点的值；堆总是一个完整的二叉树(如下图)。根节点最大的堆称为最大堆或大根堆，根节点最小的堆称为最小堆或小根堆。

完全二叉树

说到堆排序，我们不能不提到完整的二叉树。这些基本概念在互联网上随处可见。我选了最简单的。

完全二叉树：每层节点数达到除最后一层以外的最大值；在最后一层，只有右边的几个节点丢失了。

在我自己的结论中，正是因为以下两个特点。

1.只允许最后一层有空位，空位在右边，即叶子节点只能出现在最大的两层(存储方式的规律性)；2.如果i1，则树的双亲为树[i div 2](其父子节点值的正则性)；

这使得分类非常方便。

堆排序

堆排序采用大顶堆升序，小顶堆降序。

在本例中，使用降序排列的小顶部堆进行分析。

堆排序步骤如下：

1.我们将数据(49，38，65，97，76，13，27，50)设置为数组$ arr2.用array $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；$ i0$i - ){ swap($arr，$i，0)；$ ArrSize-；buildHeap($arr，$ arrSize)；}//使用array构建最小堆函数build heap ($ arr，$ arr size){//计算初始下标$index，如图，数字‘97’所在的位置，比较每个子树的父节点和子节点，将最小值存储在父节点中。//循环比较$index中的一棵树，形成$ index=int $index=0的最小堆；$ $ index-){///如果有左节点，将其下标存储为最小值$ min If($ index * 2 1 $ arr size){ $ min=$ index * 2 1；//如果有右子节点，比较左右节点的大小。如果右边的子节点较小，将其节点的下标记录为最小值$ min if($ index * 22 $ arr size){ if($ arr[$ index * 22]$ arr[$ min]){ $ min=$ index * 22；} }//比较较小的子节点和父节点。如果子节点较小，则与父节点交换位置，并更新较小的IF($ arr[$ min]$ arr[$ index]){ swap($ arr，$ min，$ index)；} } } } }//这个函数用来交换低位数组$arr中索引为$one和$ other的数据。函数交换($ arr，$一，$另一){$ tmp=$ arr [$一]；$ arr[$ one]=$ arr[$ other]；$ arr[$ other]=$ tmp；}以下是排序的最终结果：

更多对PHP相关内容感兴趣的读者可以查看本网站专题：《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》、0103010

希望本文对PHP编程有所帮助。