php 实现堆排序

堆排序原理

堆排序是一种基于二叉堆数据结构的比较排序算法。利用最大堆或最小堆的特性，将待排序数组构造成堆结构，通过反复调整堆实现排序。时间复杂度为O(n log n)，空间复杂度为O(1)。

堆排序实现步骤

构建最大堆：从最后一个非叶子节点开始，向上调整每个子树使其满足堆性质。数组下标为i的节点，其左子节点为2i+1，右子节点为2i+2。

堆调整：将堆顶元素（最大值）与末尾元素交换，缩小堆范围后重新调整堆结构，直到所有元素有序。

PHP代码实现

function heapSort(&$arr) {
    $n = count($arr);

    // 构建最大堆（初始调整）
    for ($i = floor($n/2) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }

    // 逐个提取堆顶元素
    for ($i = $n - 1; $i > 0; $i--) {
        // 移动当前堆顶到末尾
        [$arr[0], $arr[$i]] = [$arr[$i], $arr[0]];
        // 调整剩余元素的新堆
        heapify($arr, $i, 0);
    }
}

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) {
        [$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
        // 递归调整受影响的子树
        heapify($arr, $n, $largest);
    }
}

// 使用示例
$array = [12, 11, 13, 5, 6, 7];
heapSort($array);
print_r($array);

关键点说明

数组索引计算：PHP数组从0开始索引，因此左子节点为2i+1而非2i。

交换操作：使用数组解构语法[$a, $b] = [$b, $a]实现高效值交换，避免临时变量。

递归调整：当堆结构发生变化时，需要递归调整受影响的子树以维持堆性质。

性能优化建议

对于大规模数据，可考虑使用SplHeap等PHP内置堆结构替代手动实现。

迭代版heapify：对于深度较大的堆，可用循环替代递归防止栈溢出。