PHP – 堆排序 – 老迟笔记

一、概述

　
1、什么是堆

　　堆是一种特殊的树形数据结构，其每个节点都有一个值，通常提到的堆都是指一棵完全二叉树，根节点的值小于（或大于）两个子节点的值。同时，根节点的两棵子树也分别是一个堆。

　　堆排序是一种选择排序，在排序过程中，将 R[1···n] 看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和子节点之间的内在关系来选择最小元素。

　　堆一般分为大顶堆和小顶堆两种。如果根结点的关键字既大于或等于左子树的关键字值
又大于或等于右子树的关键字值，那么这个堆被称之为大顶堆。此时，堆顶元素必为最大值。

　　如果根结点的关键字既小于或等于左子树的关键字值，又小于或等于右子树的关键字值，那么这个堆被称之为小顶堆。此时，堆顶元素必为最小值。

　
2、堆排序的思想

　　堆排序的思想是对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个大顶堆，再将堆的最后一个元素与堆顶元素(即二又树的根结点)进行交换后，堆的最后一个元素即为最大记录。

　　接着将前(n-1)个元素(即不包括最大记录)重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录。

　　重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最小记录，此时可得到一个有序序列。

　
3、堆排序的算法原理

（1）将初始待排关键字序列 R[1…n] 构建成大顶堆，此堆为初始的无序区。

（2）将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 R [1···n-1] 和新的有序区 R[n]，且满足R[1…n-1] ≤ R[n]。

（3）由于交换后新的堆顶 R[1] 可能违反大顶堆的性质，因此需要对当前无序区 R[1…n-1]调整为大顶堆，然后再次将 R[1] 与无序区最后一个元素交换，得到新的无序区R[1…n-2]和新的有序区R [n，n-1]。

（4）不断重复此过程直到有序区的元素个数为(n-1)，则整个排序过程完成。

二、PHP 代码实现

<?php
declare(strict_types = 1);

class TestCase
{
    /**
     * 堆排序
     *
     * @param array $array
     * @return array
     */
    public function sortArray(array $array) : array
    {
        // 建堆
        $heapSize = count($array);
        $initI = intval(floor($heapSize / 2)) - 1;
        for ($i = $initI; $i >= 0; $i--) {
            $this->maintainHeap($array, $i, $heapSize);
        }

        // 堆排序
        for ($k = $heapSize - 1; $k >= 1; $k--) {
            $tmp = $array[0];
            $array[0] = $array[$k];
            $array[$k] = $tmp;
            $this->maintainHeap($array, 0, --$heapSize);
        }
        return $array;
    }

    /**
     * 维护堆的性质
     * 
     * @param array $array 数组
     * @param int $indexKey 数组下标
     * @param int $heapSize 堆大小
     */
    private function maintainHeap(array &$array, int $indexKey, int $heapSize)
    {
        $left = 2 * $indexKey + 1;
        $right = 2 * $indexKey + 2;
        $largest = $indexKey;
        if ($left < $heapSize && $array[$left] > $array[$largest]) {
            $largest = $left;
        }
        if ($right < $heapSize && $array[$right] > $array[$largest]) {
            $largest = $right;
        }
        if ($largest != $indexKey) {
            $tmp = $array[$indexKey];
            $array[$indexKey] = $array[$largest];
            $array[$largest] = $tmp;
            $this->maintainHeap($array, $largest, $heapSize);
        }
    }

}

// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 15, 24, 36];
$arrObject = new TestCase();
// 执行排序
$arr = $arrObject->sortArray($arr);
// 输出结果
foreach ($arr as $v) {
    echo $v . ' ';
}

// 结果
3 15 15 19 20 22 24 36 36 64 77 95

三、算法性能分析

最好情况：T(n) = O(nlogn)

最差情况：T(n) = O(nlogn)

平均情况：T(n) = O(nlogn)

打赏赞