堆可以视为一棵完全的二叉树,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素。
数组与堆之间的关系：
二叉堆一般分为两种：最大堆和最小堆。
最大堆：堆中每个父节点的元素值都大于等于其孩子结点（如果存在）；
最小堆：堆中每个父节点的元素值都小于等于其孩子结点（如果存在）；
什么是堆排序
堆排序（假设利用最大堆）就是把堆顶的最大数取出,将剩余的堆继续调整为最大堆
堆排序算法
建堆：建堆是不断调整堆的过程，从 len/2 处开始调整，一直到第一个节点，此处 len 是堆中元素的个数。建堆的过程是线性的过程，从 len/2 到 0 处一直调用调整堆的过程，相当于 o(h1) + o(h2) …+ o(hlen/2) 其中 h 表示节点的深度，len/2 表示节点的个数，这是一个求和的过程，结果是线性的 O(n)。
调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点 left(i) , right(i)，选出三者最大(或者最小)者，如果最大（小）
值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是 logn 的操作，因
为是沿着深度方向进行调整的。
堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面 len-1 个节点继续进行堆调整的过
程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是 O(nlogn)。因为建堆的时间复杂度是 O(n)（调用一次）；调整堆的时间复杂度是 logn，调
用了 n-1 次，所以堆排序的时间复杂度是O(nlogn)。
例子：
<?php// PHP 堆排序算法实现、堆排序时间复杂度分析/** * 堆排序 * @param array $arr */function heap_sort(array &$arr){ $count = count($arr); // 建堆 (下标小于或等于floor($count/2)-1的节点都是要调整的节点) for($i = floor($count / 2) - 1; $i >= 0; $i --) { heap_adjust($arr, $i, $count); } // 调整堆 for($i = $count - 1; $i >= 0; $i--) { //将堆顶元素与最后一个元素交换 swap($arr,0,$i); heap_adjust($arr,0,$i - 1); }}/** * 交换2个值 * @param array $arr * @param int $a 数组下标 * @param int $b 数组下标 */function swap(array &$arr, $a, $b){ $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp;}/** * 交换2个值 * @param array $arr * @param int $start 数组下标 * @param int $end 数组下标 */function hea<strong style="color:transparent">来2源gaodaima#com搞(代@码&网</strong><label>搞gaodaima代码</label>p_adjust(array &$arr, $start, $end){ $temp = $arr[$start]; //沿关键字较大的孩子节点向下筛选，这里数组开始下标识0 for($j = 2 * $start + 1; $j <= $end; $j = 2 * $j + 1) { if($j != $end && $arr[$j] < $arr[$j + 1]) { $j ++; } if($temp < $arr[$j]) { //将根节点设置为子节点的较大值 $arr[$start] = $arr[$j]; $start = $j; } } $arr[$start] = $temp;}// 使用$arr = array(8,4,2,9,3,7,1,6,5);heap_sort($arr);print_r($arr);
输出：
Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 [6] => 7 [7] => 8 [8] => 9 )
时间复杂度分析
总体上来说，堆排序的时间复杂度是 O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最差和平均时间复杂度都是 O(nlogn)。这在性能上显然要远远好于冒泡、简单选择、直接插入的 O(n^2) 的时间复杂度了。
堆排序是一种不稳定排序方法(排序前后相同元素的前后顺序可能改变)。
相关推荐：
JavaScript中的堆排序详解
PHP排序算法之堆排序详解
PHP堆排序算法实例详解
以上就是PHP堆排序实现代码的详细内容，更多请关注搞代码gaodaima其它相关文章！
转载请注明原文链接：PHP堆排序实现代码
