六、堆排序

原理

堆排序利用了 这种数据结构, 是大根树(或小根树)而且是一棵完全二叉树。

大根树是任意节点都大于或等于其子节点的树,小根树则是任意节点都小于或等于其子节点的树。

分为两种:大根堆(根元素是最大值) 和 小根堆(根元素是最小值),利用这一特点,只需循环取出 的根元素就可以完成排序了。

开始之前需要先了解树和堆的一些基础知识,可以先阅读此文 数据结构概览

本次排序中我们会用到堆的这些知识:

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

六、堆排序

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

步骤

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

本作品采用《CC 协议》,转载必须注明作者和本文链接
xiaer
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!