PHP排序算法之堆排序(Heap Sort)实例详解
什么是堆排序?
堆排序(Heap Sort)是一种树形选择排序,是对直接选择排序的有效改进。
堆排序的过程是将待排序的序列构建成一个大根堆(或小根堆),此时整个序列的最大(或最小)值就是堆顶的根节点。
将其与堆数组的末尾元素进行交换,此时末尾就为最大(或最小)值。
然后将剩余n-1个元素重新构造成堆,这样就会得到n个元素的次小值。
重复执行此步骤直到排序完成。
实现堆排序
1.构建大根堆
使用数组来表示堆,第一个节点是父节点,从它开始一直到最后一个节点,下标值连续增加。
堆的构建是从最后一个非叶子节点开始的,直到根节点,具体实现为:
// 建立大顶堆
function buildMaxHeap(&$arr, $heapSize)
{
// 取得最后一个非叶子节点
$lastParentNode = intval(($heapSize - 1) / 2);
// 从最后一个非叶子节点开始向上构造最大堆
for ($i = $lastParentNode; $i >= 0; $i--) {
heapify($arr, $heapSize, $i);
}
}
2.堆化过程
建立大根堆后,需要进行堆化,使堆满足最大堆的特点。
父节点的值大于它的左右子节点,但是左右子节点之间并无大小之分,所以需要比较左右子节点的大小,找出较大的一个与父节点比较。
// 堆化
function heapify(&$arr, $heapSize, $i)
{
$left = $i * 2 + 1;
$right = $i * 2 + 2;
$largest = $i;
// 比较父节点、左子节点和右子节点的大小
if ($left < $heapSize && $arr[$left] > $arr[$largest]) {
$largest = $left;
}
if ($right < $heapSize && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
// 如果最大值不是父节点,就交换位置并堆化
if ($largest != $i) {
swap($arr, $i, $largest);
heapify($arr, $heapSize, $largest);
}
}
3.堆排序实现
建立好的大根堆是按照顺序存储在数组中的,不需要再次调整节点,直接将根节点与末尾节点交换位置,便可以将末尾节点加入有序区间。
随着节点的减少,剩下的节点可能不再满足最大堆的特点,需要进行再次堆化。
// 堆排序
function heapSort(&$arr)
{
$heapSize = count($arr);
// 构建大根堆
buildMaxHeap($arr, $heapSize);
// 根节点与末尾交换,并堆化
for ($i = $heapSize - 1; $i >= 1; $i--) {
swap($arr, 0, $i);
$heapSize--;
heapify($arr, $heapSize, 0);
}
}
堆排序示例
示例1
$arr = [22, 5, 11, 41, 45, 26, 29, 10, 7, 8, 30];
// 堆排序
heapSort($arr);
// 输出
foreach ($arr as $value) {
echo "$value ";
}
输出结果为:5 7 8 10 11 22 26 29 30 41 45
示例2
$arr = [31, 24, 17, 20, 16, 19, 5, 10, 12, 4, 8, 14, 9, 7, 2];
// 堆排序
heapSort($arr);
// 输出
foreach ($arr as $value) {
echo "$value ";
}
输出结果为:2 4 5 7 8 9 10 12 14 16 17 19 20 24 31
通过两个示例可以看出,堆排序是一种十分高效的排序算法,也适用于较大的数据集。堆排序的核心是构建大根堆,并进行堆化,非常适合于排序、查找前k个最大/小值,以及优先队列等应用场景。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:PHP排序算法之堆排序(Heap Sort)实例详解 - Python技术站