当前位置：首页 > news >正文

零基础PHP从零到一手写堆排序的庖丁解牛

news 2026/6/17 2:13:23

它的本质是：堆排序不是“魔法”，而是利用数组索引的数学规律，在内存中构建一棵隐式完全二叉树 (Implicit Complete Binary Tree)，并通过下沉操作 (Sink/Heapify)维持“父节点永远大于（或小于）子节点”的秩序，从而实现高效筛选。

核心矛盾：普通排序（如冒泡）是两两比较，效率低O(n2)O(n^2)O(n2)。堆排序通过树形结构将比较次数降低到对数级O(log⁡n)O(\log n)O(logn)，总复杂度O(nlog⁡n)O(n \log n)O(nlogn)。难点在于如何将线性数组想象成立体树结构，以及如何用代码实现树的自我修复。
存在理由：
1. 空间最优 (Space Optimal)：不需要额外数组，直接在原数组上交换（原地排序）。
2. 时间稳定 (Time Stable)：无论最好、最坏、平均情况，都是O(nlog⁡n)O(n \log n)O(nlogn)，没有快排的最坏退化风险。
3. Top K 问题神器：建堆过程可以快速找到最大/最小的 K 个元素。
4. 思维升级：从“线性思维”跃迁到“树形思维”，理解索引即指针的本质。
核心逻辑：别把堆当成“复杂对象”。把它当成带有特殊规则的数组。规则只有两条：1. 父节点iii的左孩子是2i+12i+12i+1，右孩子是2i+22i+22i+2。2. 父节点必须比孩子大（大顶堆）。

如果把堆排序比作公司管理：

建堆 (Build Heap)：是组织架构调整。
- 从最后一个非叶子节点开始，向上逐个检查。
- 如果经理能力不如员工，就交换位置（下沉），确保每个小团队里老大最强。

排序 (Sort)：是末位淘汰与重组。
- 把最强的 CEO（根节点）调到最后一位（已排序区）。
- 剩下的群龙无首，重新选拔新 CEO（对根节点进行下沉修复）。
- 重复此过程，直到所有人按能力排好队。
核心价值：无需额外场地（内存），仅通过内部换位，实现有序化。

一、核心概念：什么是堆？

1. 完全二叉树 (Complete Binary Tree)

定义：除了最后一层，其他层都是满的；最后一层从左到右填充。
特性：可以用数组完美存储，没有空间浪费。

2. 大顶堆 (Max Heap) vs. 小顶堆 (Min Heap)

大顶堆：Parent >= Left Child且Parent >= Right Child。根节点是最大值。
小顶堆：Parent <= Left Child且Parent <= Right Child。根节点是最小值。
注意：堆只保证父子关系，不保证兄弟关系，也不保证左右子树的大小关系。

3. 下沉操作 (Heapify / Sink)

定义：当某个节点违反了堆性质时，将其与较大的子节点交换，并递归向下，直到满足性质或到达叶子。
作用：维护堆秩序的原子操作。

💡 核心洞察：堆的核心不是“树”，而是数组索引之间的数学关系。

二、数学映射：数组如何变树？

假设数组索引从0开始，对于任意节点i：

父节点索引：parent(i) = floor((i - 1) / 2)
左孩子索引：left(i) = 2 * i + 1
右孩子索引：right(i) = 2 * i + 2

示例：
数组[10, 5, 8, 2, 3]

索引 0 (10): 左孩子 1 (5), 右孩子 2 (8)
索引 1 (5): 左孩子 3 (2), 右孩子 4 (3)
索引 2 (8): 无孩子（超出数组范围）

10 (0) / \ 5 (1) 8 (2) / \ 2 (3) 3 (4)

PHP 隐喻：$left = 2 * $i + 1;这就是指针。

三、算法步骤：两步走战略

第一步：建堆 (Build Max Heap)

目标：将无序数组转化为大顶堆。
策略：从最后一个非叶子节点开始，向前遍历到根节点，对每个节点执行heapify。
为什么从最后一个非叶子节点？：叶子节点没有孩子，天然满足堆性质，无需处理。
最后一个非叶子节点索引：floor(n / 2) - 1。

第二步：排序 (Heap Sort)

目标：提取最大值并剩余部分重新建堆。
策略：
1. 交换根节点（最大值）与末尾节点。
2. 数组长度减 1（末尾元素已就位，不再参与堆调整）。
3. 对新的根节点执行heapify，恢复堆性质。
4. 重复直到堆大小为 1。

四、PHP 实现：从零手写

<?phpclassHeapSorter{/** * 主入口：堆排序 */publicstaticfunctionsort(array&$arr):void{$n=count($arr);if($n<=1)return;// 1. 建堆：从最后一个非叶子节点开始，自底向上调整// 最后一个非叶子节点索引: n/2 - 1for($i=intdiv($n,2)-1;$i>=0;$i--){self::heapify($arr,$n,$i);}// 2. 排序：逐个提取最大值for($i=$n-1;$i>0;$i--){// 将当前根（最大值）移到末尾self::swap($arr,0,$i);// 对剩余的 i 个元素重新调整堆// 此时堆大小变为 $i，根节点是 0self::heapify($arr,$i,0);}}/** * 核心：下沉操作 (Heapify) * @param array &$arr 数组引用 * @param int $n 堆的大小（有效元素个数） * @param int $i 需要调整的节点索引 */privatestaticfunctionheapify(array&$arr,int$n,int$i):void{$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){self::swap($arr,$i,$largest);// 递归调整被交换的子树self::heapify($arr,$n,$largest);}}/** * 辅助：交换元素 */privatestaticfunctionswap(array&$arr,int$i,int$j):void{$temp=$arr[$i];$arr[$i]=$arr[$j];$arr[$j]=$temp;}}// --- 测试 ---$data=[12,11,13,5,6,7];echo"原始数组: ".implode(', ',$data)."\n";HeapSorter::sort($data);echo"排序后: ".implode(', ',$data)."\n";?>

代码庖丁解牛：

&$arr: 使用引用传递，实现原地排序，节省内存。
intdiv($n, 2) - 1: 精准定位最后一个非叶子节点，避免无效计算。
heapify递归: 确保交换后的子树依然满足堆性质。这是分治法的体现。
$n的变化: 在排序阶段，$n逐渐减小，代表已排序区的扩大和未排序堆的缩小。

五、认知牢笼：常见误区

1. 误区：“堆排序就是快速排序。”

真相：
- 快排基于分区 (Partition)，平均O(nlog⁡n)O(n \log n)O(nlogn)但最坏O(n2)O(n^2)O(n2)。
- 堆排基于树形选择，稳定O(nlog⁡n)O(n \log n)O(nlogn)。
- 对策：理解两者底层逻辑不同。

2. 误区：“索引从 1 开始更好算。”

真相：
- 很多教材从 1 开始（左孩子2i2i2i，右孩子2i+12i+12i+1）。
- 但 PHP 数组从 0 开始。强行从 1 开始会导致索引混乱。
- 对策：牢记2*i+1和2*i+2公式。

3. 误区：“建堆是从根节点开始向下。”

真相：
- 从根开始向下无法保证子树已经是堆。
- 对策：必须自底向上，从最后一个非叶子节点开始，确保处理父节点时，子树已是合法堆。

4. 误区：“堆排序不稳定。”

真相：
- 是的，堆排序是不稳定排序（相同元素的相对顺序可能改变）。
- 对策：如果需要稳定排序，选择归并排序。

5. 误区：“递归太慢，要用循环。”

真相：
- 递归深度为log⁡n\log nlogn，非常浅，性能损耗可忽略。
- 对策：为了代码可读性，递归更佳。若追求极致，可改为 while 循环。

🚀 总结：原子化“堆排序”全景图

维度	关键点
本质	利用数组索引映射完全二叉树，通过下沉操作维持秩序的原地排序算法
核心结构	大顶堆/小顶堆，完全二叉树
数学映射	左孩子`2i+1`，右孩子`2i+2`，父节点`(i-1)/2`
关键操作	Heapify (下沉)，Build Heap (自底向上建堆)
复杂度	时间O(nlog⁡n)O(n \log n)O(nlogn)，空间O(1)O(1)O(1)
PHP 隐喻	Array Index Arithmetic & Recursive Swapping
公式	*Efficiency = N Log(N)**