堆的定义：
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：(1) ki<=k(2i) 且 ki<=k(2i+1)(1≤i≤n/2），当然，这是小根堆，大根堆则换成>=号。k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点。若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
/** * 调整堆 * @param array $arr 排序数组 * @param int $i 待调节元素的下标 * @param int $size 数组大小, 准确来说是数组最大索引值加1 */function heapAjust(& $arr, $i, $size){ $key = $arr[$i]; // 索引从0开始 // 左孩子节点为 2i+1, 右孩子节点为 2i+2 for($j = 2 * $i + 1; $j < $<strong style="color:transparent">来2源gaodaima#com搞(代@码&网</strong><label>搞gaodaima代码</label>size; $j = 2 * $j + 1) { if($j + 1 < $size && $arr[$j] < $arr[$j + 1]) $j++; if($key > $arr[$j]) break ; $arr[$i] = $arr[$j]; //调换值 $i = $j; } $arr[$i] = $key;}/** * 堆排序 * 时间复杂度：O(nlogn) * 不稳定的排序算法 */function heapSort(& $arr){ $len = count($arr); // 构建初始大根堆 for($i = intval($len/2); $i >= 0; $i--) { heapAjust($arr, $i, $len); } // 调换堆顶元素和最后一个元素 for($j = $len - 1; $j > 0; $j--) { $swap = $arr[0]; $arr[0] = $arr[$j]; $arr[$j] = $swap; heapAjust($arr, 0, $j); //继续调整剩余元素为大根堆 }}
以上就是PHP实现堆排序的方法详解的详细内容，更多请关注搞代码gaodaima其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：PHP实现堆排序的方法详解
转载请注明原文链接：PHP实现堆排序的方法详解
