堆排序在PHP中实现的核心是利用数组模拟完全二叉树，通过大根堆（升序）或小根堆（降序）进行原地排序，时间复杂度O(n log n)、空间复杂度O(1)；关键步骤包括建堆（自底向上heapify）、交换堆顶与末尾、缩小堆范围并重新堆化。
堆排序在PHP中实现，核心在于理解“完全二叉树”的数组表示和“堆化”逻辑。它不依赖额外空间（原地排序），时间复杂度稳定为 O(n log n)，适合对性能和内存有要求的场景。
堆排序的关键前提：什么是堆？
堆是一个满足特定条件的完全二叉树，用一维数组存储即可：
- 大根堆：每个节点值 ≥ 其左右子节点值 → 适合升序排列（每次把最大值换到末尾）
- 小根堆：每个节点值 ≤ 其左右子节点值 → 适合降序排列
- 父子下标关系固定（数组索引从 0 开始）：
– 节点 i 的左子节点在 2*i + 1，右子节点在 2*i + 2
– 节点 i 的父节点在 floor((i−1)/2)
PHP8.1 堆排序四步走（升序，用大根堆）
以数组 [64, 34, 25, 12, 22, 11, 90] 为例：
-
建堆（自底向上调整）：从最后一个非叶子节点（
floor(n/2) − 1）开始，对每个节点执行向下调整（heapify），确保子树满足大根堆性质 - 交换堆顶与末尾：将堆顶（当前最大值）与未排序区末尾元素互换
- 缩小堆范围：已排序元素不再参与堆调整，堆有效长度减 1
- 重新堆化：对新堆顶执行一次向下调整，恢复大根堆结构，重复步骤 2–4 直至堆只剩 1 个元素
可直接运行的 PHP8.1 实例代码
以下为简洁、无依赖、符合 PSR-12 风格的完整实现：
<?php function heapSort(array $arr): array
{
$n = count($arr);
if ($n <= 1) return $arr;
<pre class="brush:php;toolbar:false;">// 步骤1：建大根堆（从最后一个非叶子节点开始）
for ($i = (int)($n / 2) - 1; $i >= 0; $i--) {
heapify($arr, $n, $i);
}
// 步骤2：逐个取出堆顶，放至末尾
for ($i = $n - 1; $i > 0; $i--) {
[$arr[0], $arr[$i]] = [$arr[$i], $arr[0]]; // 交换
heapify($arr, $i, 0); // 对剩余 $i 个元素重新堆化
}
return $arr;
}
function heapify(array &$arr, int $heapSize, int $root): void { $largest = $root; $left = 2 $root + 1; $right = 2 $root + 2;
if ($left $arr[$largest]) {
$largest = $left;
}
if ($right $arr[$largest]) {
$largest = $right;
}
if ($largest !== $root) {
[$arr[$root], $arr[$largest]] = [$arr[$largest], $arr[$root]];
heapify($arr, $heapSize, $largest);
}
}
// 测试 $data = [64, 34, 25, 12, 22, 11, 90]; print_r(heapSort($data)); // 输出：[11, 12, 22, 25, 34, 64, 90] ?>
常见易错点提醒
写堆排序时，这几个细节容易出错：
- 建堆起始索引是
(int)($n / 2) - 1，不是$n / 2或$n - 1 - 向下调整中，比较前必须先检查子节点索引是否越界（
$left ） - 交换后调用
heapify($arr, $i, 0)—— 第二参数是当前堆大小（不是原始 $n），否则会污染已排序段 - PHP8.1 支持解构赋值
[$a, $b] = [$b, $a]，比临时变量更安全，避免引用错误
php免费学习视频：立即使用
踏上前端学习之旅，开启通往精通之路！从前端基础到项目实战，循序渐进，一步一个脚印，迈向巅峰！
