常见算法 PHP 实现 -- 堆排序
昨晚又重新看了看以前一直没仔细研究的堆排序,记录篇文章,把思路记录一下。欢迎大家访问我的博客。(荒废了好久的博客又开张了,这次用的是 gitpage,静态网站生成器用的是 hugo )
废话不多说,进入正文
什么是堆
通俗点讲,堆(英语:Heap)是具有以下性质的完全二叉树,任意节点小于(或大于)它的左右子节点,最小值(或大值)在根元素位置。我们称最小值在根节点(堆顶)的叫做小根(顶)堆,最大值在根节点(堆顶)的叫做大根(顶)堆。
总结性质如下:
- 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
- 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
二叉树性质
除了堆的定义外,我们还需要了解一些树的基本性质,下面代码会用到这些。
我们假设一个数组的第一个元素(索引为 0)位于根节点,那么可以得出一下定义:
- 任意节点 i 的左节点索引是 : 2 * i + 1
- 任意节点 i 的右节点索引是 : 2 * i + 2
- 最后一个非叶子节点的索引是 : floor(length / 2) - 1
堆排序
有了上面这些基础后,我们就可以开始介绍一下堆排序的整体思路了。
-
将待排序数组
(R0,R2....Rn)
构建为一个大(小)根堆; -
将堆顶元素
R[0]
与最后一个元素R[n]
交换,此时得到一个新的无序区(R0,R2,......Rn-1)
和新的有序区(Rn)
,且满足R[0,2...n-1] <= R[n]
; -
此时堆顶的元素
R[0]
有可能违反堆的性质,因此我们需要重新重复第一步的操作,将(R0,R2,......Rn-1)
重新构建为大(小)根堆; -
循环执行上面的过程,直到有序区的元素为
n
,则排序完成。
对于堆排序,最重要的两个操作就是
构造初始堆
和调整堆
,其实构造初始堆也是调整堆的过程,只不过构造初始堆是对所有的非叶节点都进行调整,调整堆则只需要对堆顶元素R[0]
做向下调整。
代码实现
代码实现分为两部分,第一部分我们介绍如果把无序的数组调整为一个符合堆性质的数组
-
对于第一次构建堆,我们选择从第一个非叶子节点开始调整,一直循环到根节点为止
-
对于调整堆,我们只需要从根节点开始,做一次调整就够了,因为除了根节点外,其他的节点是满足根节点性质的
上面描述的有点抽象,最好可以画一个树,然后一个节点一个节点调整。最难理解的大概就是构建堆的过程了。
/**
* 构建堆
*
* @param [array] $arr [待排序无序数组]
* @param [int] $start [第一个需要调整的非叶子节点]
* @param [int] $len [元素个数]
*
* @return void
*/
function heapAdjust(&$arr, $start, $len)
{
for ($child = $start * 2 + 1; $child < $len; $child = $child * 2 + 1) {
//左节点小于右节点
if ($child != $len - 1 && $arr[$child] < $arr[$child + 1]) {
$child++; //此时子节点指向右子节点
}
//满足大顶(根)堆
if ($arr[$start] >= $arr[$child]) {
break;
}
//和子节点进行交换
list($arr[$start], $arr[$child]) = array($arr[$child], $arr[$start]);
$start = $child;
}
}
第二步,我们来看看具体排序实现
/**
* [heapSort 堆排序实现]
*
* @param [array] $arr [待排序的无序数组]
*
* @return void
*/
function heapSort(&$arr)
{
/**
* 将待排序数组构建成一个大顶(根)堆
* 构建说明:从最后(下)一个非叶子节点,比较当前节点和子节点,找到最小的点,进行交换,
* 循环向堆顶递进,最后就形成了一个大顶(根)堆
*/
$len = count($arr);
//第一次构建堆,我们从第一个非叶子节点开始调整一直循环到根节点为止,则构造完成
for ($i = ($len >> 1) - 1; $i >= 0; $i--) {
heapAdjust($arr, $i, $len);
}
for ($i = $len - 1; $i >= 0; $i--) {
//交换根顶和根尾元素
list($arr[0], $arr[$i]) = array($arr[$i], $arr[0]);
//调整堆,我们只需要从根节点开始向下调整
heapAdjust($arr, 0, $i);
}
}
时间复杂度与空间复杂度
堆执行一次调整需要O(logn)的时间,在排序过程中需要遍历所有元素执行堆调整,所以最终时间复杂度是O(nlogn)。空间复杂度是O(1)。
总结
对堆排序理解的难点,大部分在于构建堆的过程的理解上,为何从第一个非叶子节点开始和子节点进行交换,一直循环到根顶,这个构建过程还需要亲手画画图,理解的会比较深。
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: