如何实现PHP中的堆排序（Heap Sort）算法？详解实例带你掌握！

PHP排序算法之堆排序(Heap Sort)实例详解

1. 什么是堆排序？

堆排序是一种基于比较的排序算法，利用堆这种数据结构来实现，堆是一种特殊的完全二叉树，分为最大堆和最小堆，在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值，堆排序通常使用最大堆来进行升序排序，使用最小堆来进行降序排序。

2. 堆排序的基本步骤

堆排序可以分为两个主要步骤：

1、构建初始堆：将无序数组构建成一个最大堆。

2、排序过程：反复将堆顶元素（最大值）与堆的最后一个元素交换，然后重新调整堆，直到整个数组有序。

3. 代码实现

1 构建最大堆

function buildMaxHeap(&$arr, $n) {
    for ($i = floor($n / 2)  1; $i >= 0; $i) {
        heapify($arr, $n, $i);
    }
}
function heapify(&$arr, $n, $i) {
    $largest = $i; // 初始化最大值为根节点
    $left = 2 * $i + 1; // 左子节点
    $right = 2 * $i + 2; // 右子节点
    // 如果左子节点存在且大于根节点
    if ($left < $n && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }
    // 如果右子节点存在且大于当前最大值
    if ($right < $n && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }
    // 如果最大值不是根节点
    if ($largest != $i) {
        // 交换根节点和最大值节点
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;
        // 递归地对受影响的子树进行堆化
        heapify($arr, $n, $largest);
    }
}

2 堆排序主函数

function heapSort(&$arr) {
    $n = count($arr);
    // 构建最大堆
    buildMaxHeap($arr, $n);
    // 一个接一个地从堆中取出元素
    for ($i = $n  1; $i >= 0; $i) {
        // 移动当前根到末尾
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;
        // 调用heapify来减少堆的大小并重新构建堆
        heapify($arr, $i, 0);
    }
}

3 测试代码

$arr = [12, 11, 13, 5, 6, 7];
heapSort($arr);
echo "Sorted array is \n";
print_r($arr);

4. 示例输出

Sorted array is 
Array
(
    [0] => 5
    [1] => 6
    [2] => 7
    [3] => 11
    [4] => 12
    [5] => 13
)

5. 相关问题与解答

Q1: 堆排序的时间复杂度是多少？

A1: 堆排序的时间复杂度为O(n log n)，其中n是数组的长度，这是因为构建初始堆需要O(n)时间，而每次从堆中取出元素并重新调整堆需要O(log n)时间，总共需要进行n次这样的操作。

Q2: 堆排序的空间复杂度是多少？

A2: 堆排序的空间复杂度为O(1)，因为它是一个原地排序算法，不需要额外的存储空间。

以上就是关于“PHP排序算法之堆排序(Heap Sort)实例详解”的问题，朋友们可以点击主页了解更多内容，希望可以够帮助大家!