堆可以视为一棵完全的二叉树,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素。
数组与堆之间的关系:
二叉堆一般分为两种:最大堆和最小堆。
最大堆:堆中每个父节点的元素值都大于等于其孩子结点(如果存在);
最小堆:堆中每个父节点的元素值都小于等于其孩子结点(如果存在);
堆排序(假设利用最大堆)就是把堆顶的最大数取出,将剩余的堆继续调整为最大堆
建堆:建堆是不断调整堆的过程,从 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 heap_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) 的时间复杂度了。
堆排序是一种不稳定排序方法(排序前后相同元素的前后顺序可能改变)。
相关推荐:
以上是PHP堆排序实现代码的详细内容。更多信息请关注PHP中文网其他相关文章!