数据结构概览。本次排序中我们会用到堆的这些知识：

1. 堆是一棵完全二叉树，具备完全二叉树的特点：
2. 用数组来存储所有节点时，可以保证没有间隙。
3. 父节点与左子节点的索引满足：parent x 2 + 1 = left_child
4. 父节点与右子节点的索引满足：parent x 2 + 2 = right_child
5. 最后一个节点的索引：last = n - 1
6. 最后一个节点的父节点索引：parent = (last - 1) ÷ 2

1. 堆的基本操作：
2. 初始化一个堆，需要两层循环：
3. 第一层循环：从最后一个节点的父节点开始，每次减一，直到到达根节点。
4. 第二层循环：父节点与左右子节点比较，与比自己大的子节点交换，并逐级往下做同样的比较，直到父节点同时大于左右子节点为止。
5. 弹出根节点：
6. 取出根节点的值，然后将最后一个节点的值放到根节点处。
7. 从新的根节点开始，父节点与左右子节点比较，与比自己大的子节点交换，并逐级往下做同样的比较，直到父节点同时大于左右子节点为止。

步骤

1. 将给定的数组初始化为大根堆，这里需要用到堆的初始化操作：
2. 第一层循环：从最后一个节点的父节点开始，每次减一，直到到达根节点。
3. 第二层循环：父节点与左右子节点比较，与比自己大的子节点交换，并逐级往下做同样的比较，直到父节点同时大于左右子节点为止。
4. 将堆的根节点与末尾节点的值交换，并将堆的长度标识减一，这样做相当于弹出了堆的根节点。
5. 此时用新的根节点和左右子节点比较，与比自己大的子节点交换，并逐级往下做同样的比较，直到父节点同时大于左右子节点为止。
6. 重复 2、3 步，直到堆的长度缩减为 0。

此图来自：runoob.com 堆排序

代码

这里将堆的 初始化操作 和 父子节点逐层比较操作 分别写到了两个子方法中，条理更加清晰。

<?php declare(strict_types=1);

class Algorithm
{
    // 一、初始化大根堆（从下往上全盘整理） 
    public function initMaxHeap(array &$s, int $end): void
    {
        // $parent 最开始是末尾节点的父节点 
        for ($parent = intval(($end-1)/2); $parent >= 0; $parent--) {
            $child = $parent * 2 + 1; // 左子节点 
            $child+1 <= $end and $s[$child] < $s[$child+1] and $child++; // 若存在右子节点，就取左右中的较大者 
            if ($s[$parent] < $s[$child]) { // 与父子节点比较
                [$s[$parent], $s[$child]] = [$s[$child], $s[$parent]];
                $this->heapfiy($s, $end, $child);
            }
        }
    }

    // 二、父子节点逐层比较（由上往下分支整理） 
    public function heapfiy(array &$s, int $end, int $parent): void
    {
        for (; $parent * 2 + 1 <= $end; $parent = $child) {
            $child = $parent * 2 + 1;
            $child+1 <= $end and $s[$child] < $s[$child+1] and $child++;
            if ($s[$parent] > $s[$child]) break;
            [$s[$parent], $s[$child]] = [$s[$child], $s[$parent]];
        }
    }

    public function heapSort(array $s): array
    {
        $end = count($s) - 1;
        if ($end <= 0) return $s;

        $this->initMaxHeap($s, $end);

        // 三、把堆顶换到末尾，递减堆长度，整理出排序 
        while ($end >= 0) {
            [$s[0], $s[$end]] = [$s[$end], $s[0]];
            $end--;
            $this->heapfiy($s, $end, 0);
        }

        return $s;
    }
}

时间复杂度

堆初始化的双层循环时间复杂度是 O(nlog₂n)， 加上弹出根节点的双层循环也是 O(nlog₂n)，最终的时间复杂度为：O(nlog₂n)

最好情况和最坏情况时间复杂度均为：O(nlog₂n)

经测试，堆排序的速度比快速排序的速度还要快一些，虽然时间复杂度同为 O(nlog₂n) ，但是由于堆排序项系数等综合值小于快速排序，因此还是要快一些。

空间复杂度

循环中并无开辟并占据内存空间，所以空间复杂度为：O(1)