常见算法 PHP 实现 -- 堆排序

什么是堆

通俗点讲，堆（英语：Heap）是具有以下性质的完全二叉树，任意节点小于（或大于）它的左右子节点，最小值（或大值）在根元素位置。我们称最小值在根节点（堆顶）的叫做小根（顶）堆，最大值在根节点（堆顶）的叫做大根（顶）堆。

总结性质如下：

任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

二叉树性质

除了堆的定义外，我们还应该清楚一些树的基本性质。

我们假设一个数组的第一个元素（索引为 0）位于根节点，那么可以得出一下定义：

任意节点 i 的左节点索引是： 2 * i + 1
任意节点 i 的右节点索引是： 2 * i + 2
最后一个非叶子节点的索引是： floor(length / 2) - 1

堆排序

有了上面这些基础后，我们就可以开始介绍一下堆排序的整体思路了。

将待排序数组 (R0,R2....Rn) 构建为一个大（小）根堆；
将堆顶元素 R[0] 与最后一个元素 R[n] 交换，此时得到一个新的无序区 (R0,R2,......Rn-1) 和新的有序区 (Rn)，且满足 R[0,2...n-1] <= R[n];
此时堆顶的元素 R[0] 有可能违反堆的性质，因此我们需要重新重复第一步的操作，将 (R0,R2,......Rn-1) 重新构建为大（小）根堆；
循环执行上面的过程，直到有序区的元素为 n，则排序完成。

对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整，调整堆则只需要对堆顶元素 R[0] 做向下调整。

代码实现

代码实现分为两部分，第一部分我们介绍如果把无序的数组调整为一个符合堆性质的数组

对于第一次构建堆，我们选择从第一个非叶子节点开始调整，一直循环到根节点为止
对于调整堆，我们只需要从根节点开始，做一次调整就够了，因为除了根节点外，其他的节点是满足根节点性质的

上面描述的有点抽象，最好可以画一个树，然后一个节点一个节点调整。最难理解的大概就是构建堆的过程了。

/**
 * 构建堆
 *
 * @param  [array] $arr  [待排序无序数组]
 * @param  [int] $start [第一个需要调整的非叶子节点]
 * @param  [int] $len  [元素个数]
 *
 * @return void
 */
function heapAdjust(&$arr, $start, $len)
{

    for ($child = $start * 2 + 1; $child < $len; $child = $child * 2 + 1) {
        //左节点小于右节点
        if ($child != $len - 1 && $arr[$child] < $arr[$child + 1]) {
            $child++;  //此时子节点指向右子节点
        }

        //满足大顶（根）堆
        if ($arr[$start] >= $arr[$child]) {
            break;
        }

        //和子节点进行交换
        list($arr[$start], $arr[$child]) = array($arr[$child], $arr[$start]);

        $start = $child;
    }
}

第二步，我们来看看具体排序实现

/**
 * [heapSort 堆排序实现]
 *
 * @param  [array] $arr [待排序的无序数组]
 *
 * @return void
 */
function heapSort(&$arr) 
{
    /**
     * 将待排序数组构建成一个大顶（根）堆
     * 构建说明：从最后（下）一个非叶子节点，比较当前节点和子节点，找到最小的点，进行交换，
     * 循环向堆顶递进，最后就形成了一个大顶（根）堆
     */
    $len = count($arr);

    //第一次构建堆，我们从第一个非叶子节点开始调整一直循环到根节点为止，则构造完成
    for ($i = ($len >> 1) - 1; $i >= 0; $i--) {
        heapAdjust($arr, $i, $len);
    }

    for ($i = $len - 1; $i >= 0; $i--) {
        //交换根顶和根尾元素
        list($arr[0], $arr[$i]) = array($arr[$i], $arr[0]);

        //调整堆，我们只需要从根节点开始向下调整
        heapAdjust($arr, 0, $i);
    }
}

时间复杂度与空间复杂度

堆执行一次调整需要O(logn)的时间，在排序过程中需要遍历所有元素执行堆调整，所以最终时间复杂度是O(nlogn)。空间复杂度是O(1)。

总结

对堆排序理解的难点，大部分在于构建堆的过程的理解上，为何从第一个非叶子节点开始和子节点进行交换，一直循环到根顶，这个构建过程还需要亲手画画图，理解的会比较深。

Contents

什么是堆

二叉树性质

堆排序

代码实现

时间复杂度与空间复杂度

总结