数据结构与算法之PHP排序算法（堆排序）
一、堆的定义
堆通常是一个可以被看做一棵树的数组对象，其任一非叶节点满足以下性质：
1）堆中某个节点的值总是不大于或不小于其父节点的值：
每个节点的值都大于或等于其左右子节点的值，称为大顶堆。即：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]。
或：
每个节点的值都小于或等于其左右子节点的值，称为小顶堆。即：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]。
2）堆总是一棵完全二叉树。
注：上述公式，根节点从0开始。如果根节点从1开始，则左右子节点分别是2i和2i+1。
由上述性质可知：堆顶元素（或完全二叉树的根）必定是所有元素中最大值（大顶堆）或最小值（小顶堆）。
二、基本思想
以大顶堆为例，将待排序的序列构造成一个大根堆，此时，整个序列的最大值就是堆顶的根节点。将它移走（也就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小的值。如此反复执行，便能得到一个有序序列了。
三、算法过程
1）将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2）将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3）重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
以大顶堆为例，
创建堆：
1）将n个元素从0到n-1（或从1到n）自顶向下、从左到右编码，转换成一棵完全二叉树；
2）从n/2的非叶节点开始到根节点，逐个扫描，如果子节点大于父节点，就交换；
3）直到根节点最大，如果子树不满足最大堆的条件，继续调节，直到所有的父节点都大于子节点为止。
堆排序：
1）排序开始，首先输出堆顶元素，因为它是最大值；
2）将堆顶元素和最后一个元素交换；
3）将前面n-1个节点继续进行堆调整的过程，再将根节点取出，交换堆顶和最后一个元素；
4）这样一直到所有节点都取出，则排序完成。
四、算法图解
待排序序列为49、38、65、97、76、13、27、50，其逻辑结构和存储结构如下：
1)构造大顶堆
① 从最后一个非叶子节点开始，第一个非叶子节点 arr.length/2-1=8/2-1=3，也就是97，在[97, 50]这个小堆里边,父节点97最大，所以不交换；
② 找到第2个非叶子节点，也就是位置为2的节点65，在[65, 13, 27]这个小堆里边,父节点65最大，所以不交换；
③ 找到第3个非叶子节点，也就是位置为1的节点38，在[38, 97, 76]这个小堆里边，97最大，38和97交换；
④ 找到第4个非叶子节点，也就是位置为0的节点49，在[49, 97, 65]这个小堆里边，97最大，49和97交换；
⑤ 交换导致了子根[49, 38, 76]结构混乱，继续调整，[49, 38, 76]中76最大，49和76交换；
⑥ 子根[38, 50]结构混乱，继续调整，[38, 50]中50最大，38和50交换；
至此，一个无序序列已经构造成一个大顶堆。
2)堆排序
① 将堆顶元素97和末尾元素38进行交换，得到最大元素97；
② 重新调整结构，使其继续满足大顶堆的定义；
③ 再将堆顶元素76与末尾元素27进行交换，得到第二大元素76；
④ 重新调整结构，使其继续满足大顶堆的定义；
⑤ 后续过程，继续进行交换、调整，如此反复进行，最终使得整个序列有序。
由排序过程可知：若想得到升序，则建立大顶堆，若想得到降序，则建立小顶堆。
五、PHP代码实现（大顶堆）
<?php
// 堆排序
function heapSort(&$arr) {
$len = count($arr);
// 先将数组构造成大根堆
for ($i = floor($len / 2) - 1; $i >= 0; $i--) {
adjustHeap($arr, $i, $len);
}
// 调整堆结构+交换堆顶元素与末尾元素
for ($j = $len - 1; $j > 0; $j--) {
swap($arr, 0, $j); // 将堆顶元素与末尾元素进行交换
adjustHeap($arr, 0, $j); // 重新对堆进行调整
}
}
// 调整堆
function adjustHeap(&$arr, $i, $length) {
$temp = $arr[$i]; // 先取出当前元素
for ($k = 2 * $i + 1; $k < $length; $k = 2 * $k + 1) {// 左孩子2 * $i + 1，右孩子2 * $i + 2
if ($k + 1 < $length && $arr[$k] < $arr[$k + 1]) {// 如果左子结点小于右子结点，k指向右子结点
$k ++;
}
if ($temp < $arr[$k]) {
$arr[$i] = $arr[$k]; // 将根节点设置为子节点的较大值
$i = $k; // 继续往下
} else {
break; // 已经满足大根堆
}
}
$arr[$i] = $temp; // 将temp值放到最终的位置
}
// 交换2个值
function swap(&$arr, $a, $b) {
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
// 测试
$arr = array(49, 38, 65, 97, 76, 13, 27, 50);
heapSort($arr);
print_r($arr);
六、效率分析
1、时间复杂度：O(nlogn)
最坏，最好，平均时间复杂度均为O(nlogn)。
2、空间复杂度：堆排序仅需一个记录大小的供交换用的辅助存储空间，因此空间复杂度为O(1)，是不稳定排序。
① 从最后一个非叶子节点开始，第一个非叶子节点 arr.length/2-1=8/2-1=3，也就是97，在[97, 50]这个小堆里边,父节点97最大，所以不交换；
② 找到第2个非叶子节点，也就是位置为2的节点65，在[65, 13, 27]这个小堆里边,父节点65最大，所以不交换；
③ 找到第3个非叶子节点，也就是位置为1的节点38，在[38, 97, 76]这个小堆里边，97最大，38和97交换；
④ 找到第4个非叶子节点，也就是位置为0的节点49，在[49, 97, 65]这个小堆里边，97最大，49和97交换；
⑤ 交换导致了子根[49, 38, 76]结构混乱，继续调整，[49, 38, 76]中76最大，49和76交换；
⑥ 子根[38, 50]结构混乱，继续调整，[38, 50]中50最大，38和50交换；
至此，一个无序序列已经构造成一个大顶堆。
2)堆排序
① 将堆顶元素97和末尾元素38进行交换，得到最大元素97；
② 重新调整结构，使其继续满足大顶堆的定义；
③ 再将堆顶元素76与末尾元素27进行交换，得到第二大元素76；
④ 重新调整结构，使其继续满足大顶堆的定义；
⑤ 后续过程，继续进行交换、调整，如此反复进行，最终使得整个序列有序。
由排序过程可知：若想得到升序，则建立大顶堆，若想得到降序，则建立小顶堆。
五、PHP代码实现（大顶堆）
<?php
// 堆排序
function heapSort(&$arr) {
$len = count($arr);
// 先将数组构造成大根堆
for ($i = floor($len / 2) - 1; $i >= 0; $i--) {
adjustHeap($arr, $i, $len);
}
// 调整堆结构+交换堆顶元素与末尾元素
for ($j = $len - 1; $j > 0; $j--) {
swap($arr, 0, $j); // 将堆顶元素与末尾元素进行交换
adjustHeap($arr, 0, $j); // 重新对堆进行调整
}
}
// 调整堆
function adjustHeap(&$arr, $i, $length) {
$temp = $arr[$i]; // 先取出当前元素
for ($k = 2 * $i + 1; $k < $length; $k = 2 * $k + 1) {// 左孩子2 * $i + 1，右孩子2 * $i + 2
if ($k + 1 < $length && $arr[$k] < $arr[$k + 1]) {// 如果左子结点小于右子结点，k指向右子结点
$k ++;
}
if ($temp < $arr[$k]) {
$arr[$i] = $arr[$k]; // 将根节点设置为子节点的较大值
$i = $k; // 继续往下
} else {
break; // 已经满足大根堆
}
}
$arr[$i] = $temp; // 将temp值放到最终的位置
}
// 交换2个值
function swap(&$arr, $a, $b) {
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
// 测试
$arr = array(49, 38, 65, 97, 76, 13, 27, 50);
heapSort($arr);
print_r($arr);
六、效率分析
1、时间复杂度：O(nlogn)
最坏，最好，平均时间复杂度均为O(nlogn)。
2、空间复杂度：堆排序仅需一个记录大小的供交换用的辅助存储空间，因此空间复杂度为O(1)，是不稳定排序。