堆排序利用堆的特性对数组进行排序。它涉及构建一个用于递增顺序排序的最大堆，其中在根处包含堆的最大元素。对于降序排序，使用最小堆，它在根处包含堆的最小元素。堆排序的升序排序的过程步骤总结如下:
- 第1步:构建一个最大堆，其中根部包含堆的最大元素
- 第2步: 将堆的最后一个元素与根元素交换，并从堆中删除最后一个元素。对其余元素重复步骤 1。
示例:
要了解堆排序，让我们考虑一个未排序的数组[10, 1, 23, 50, 7, -4] 并讨论按升序对数组进行排序所采取的每个步骤。
下图中显示了输入数组和最大堆的堆结构。堆的根元素的索引号为0。在最大堆中，堆的最大元素始终位于根。
构建初始最大堆后，堆的最后一个元素与根元素以及包含数组中最大的数将从堆中删除。之后，对堆中剩余的元素使用heapify函数，使其成为最大堆，元素数量将减少1。这个过程一直持续到堆中的元素数量为1。此时，数组将被排序。
上图描述了从堆中消除最大元素以及从堆的剩余元素形成最大堆。该过程的最终结果是一个升序排序的数组。
堆排序的实现
<?php
// 调用heapify函数的堆排序函数
//构建最大堆，然后交换最后一个元素
// 第一个元素的最大堆
//从堆中排除最后一个元素并重建堆
function heapsort(&$Array, $n) {
for($i = (int)($n/2); $i >= 0; $i--) {
heapify($Array, $n-1, $i);
}
for($i = $n - 1; $i >= 0; $i--) {
//将最大堆的最后一个元素与第一个元素交换
$temp = $Array[$i];
$Array[$i] = $Array[0];
$Array[0] = $temp;
//从堆中排除最后一个元素并重建堆
heapify($Array, $i-1, 0);
}
}
// heapify函数用于构建最大堆
//最大堆在根处有最大元素，这意味着
//数组的第一个元素将是最大堆中的最大值
function heapify(&$Array, $n, $i) {
$max = $i;
$left = 2*$i + 1;
$right = 2*$i + 2;
//如果左边元素大于根
if($left <= $n && $Array[$left] > $Array[$max]) {
$max = $left;
}
//如果右侧元素大于根
if($right <= $n && $Array[$right] > $Array[$max]) {
$max = $right;
}
//如果最大值不是i
if($max != $i) {
$temp = $Array[$i];
$Array[$i] = $Array[$max];
$Array[$max] = $temp;
//递归地堆化受影响的子树
heapify($Array, $n, $max);
}
}
//打印数组的函数
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
//测试代码
$MyArray = array(10, 1, 23, 50, 7, -4);
$n = sizeof($MyArray);
echo "原始数组\n";
PrintArray($MyArray, $n);
heapsort($MyArray, $n);
echo "\n排序数组\n";
PrintArray($MyArray, $n);
?> 上面的代码将给出以下输出:
原始数组
10 1 23 50 7 -4
排序数组
-4 1 7 10 23 50 时间复杂度:
创建堆的时间复杂度为θ(N)，创建最大堆的时间复杂度为θ(logN) em> 堆排序的总体时间复杂度为 θ(NlogN)。