PHP排序算法之堆排序(Heap Sort)实例详解

什么是堆排序？

堆排序（Heap Sort）是一种树形选择排序，是对直接选择排序的有效改进。

堆排序的过程是将待排序的序列构建成一个大根堆（或小根堆），此时整个序列的最大（或最小）值就是堆顶的根节点。

将其与堆数组的末尾元素进行交换，此时末尾就为最大（或最小）值。

然后将剩余n-1个元素重新构造成堆，这样就会得到n个元素的次小值。

重复执行此步骤直到排序完成。

实现堆排序

1.构建大根堆

使用数组来表示堆，第一个节点是父节点，从它开始一直到最后一个节点，下标值连续增加。

堆的构建是从最后一个非叶子节点开始的，直到根节点，具体实现为：

// 建立大顶堆
function buildMaxHeap(&$arr, $heapSize)
{
    // 取得最后一个非叶子节点
    $lastParentNode = intval(($heapSize - 1) / 2);

    // 从最后一个非叶子节点开始向上构造最大堆
    for ($i = $lastParentNode; $i >= 0; $i--) {
        heapify($arr, $heapSize, $i);
    }
}

2.堆化过程

建立大根堆后，需要进行堆化，使堆满足最大堆的特点。

父节点的值大于它的左右子节点，但是左右子节点之间并无大小之分，所以需要比较左右子节点的大小，找出较大的一个与父节点比较。

// 堆化
function heapify(&$arr, $heapSize, $i)
{
    $left = $i * 2 + 1;
    $right = $i * 2 + 2;
    $largest = $i;

    // 比较父节点、左子节点和右子节点的大小
    if ($left < $heapSize && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }
    if ($right < $heapSize && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    // 如果最大值不是父节点，就交换位置并堆化
    if ($largest != $i) {
        swap($arr, $i, $largest);
        heapify($arr, $heapSize, $largest);
    }
}

3.堆排序实现

建立好的大根堆是按照顺序存储在数组中的，不需要再次调整节点，直接将根节点与末尾节点交换位置，便可以将末尾节点加入有序区间。

随着节点的减少，剩下的节点可能不再满足最大堆的特点，需要进行再次堆化。

// 堆排序
function heapSort(&$arr)
{
    $heapSize = count($arr);

    // 构建大根堆
    buildMaxHeap($arr, $heapSize);

    // 根节点与末尾交换，并堆化
    for ($i = $heapSize - 1; $i >= 1; $i--) {
        swap($arr, 0, $i);
        $heapSize--;
        heapify($arr, $heapSize, 0);
    }
}

堆排序示例

示例1

$arr = [22, 5, 11, 41, 45, 26, 29, 10, 7, 8, 30];

// 堆排序
heapSort($arr);

// 输出
foreach ($arr as $value) {
    echo "$value ";
}

输出结果为：5 7 8 10 11 22 26 29 30 41 45

示例2

$arr = [31, 24, 17, 20, 16, 19, 5, 10, 12, 4, 8, 14, 9, 7, 2];

// 堆排序
heapSort($arr);

// 输出
foreach ($arr as $value) {
    echo "$value ";
}

输出结果为：2 4 5 7 8 9 10 12 14 16 17 19 20 24 31

通过两个示例可以看出，堆排序是一种十分高效的排序算法，也适用于较大的数据集。堆排序的核心是构建大根堆，并进行堆化，非常适合于排序、查找前k个最大/小值，以及优先队列等应用场景。