优先队列及堆排序

    堆排序属于选择类排序算法。

    优先队列是一种能完成以下任务的队列：插入一个数值，取出最小或最大的数值（获取数值，并且删除）。

    优先队列可以用二叉树来实现，我们称这种结构为二叉堆。

    最小堆和最大堆是二叉堆的一种，是一棵完全二叉树（一种平衡树）。

    最小堆的性质：

    1. 父节点的值都小于左右儿子节点。
    2. 这是一个递归的性质。

    最大堆的性质：

    1. 父节点的值都大于左右儿子节点。
    2. 这是一个递归的性质。

    最大堆和最小堆实现方式一样，只不过根节点一个是最大的，一个是最小的。

    1.1. 最大堆特征

    最大堆实现细节(两个操作)：

    1. push：向堆中插入数据时，首先在堆的末尾插入数据，如果该数据比父亲节点还大，那么交换，然后不断向上提升，直到没有大小颠倒为止。
    2. pop：从堆中删除最大值时，首先把最后一个值复制到根节点上，并且删除最后一个数值，然后和儿子节点比较，如果值小于儿子，与儿子节点交换，然后不断向下交换， 直到没有大小颠倒为止。在向下交换过程中，如果有两个子儿子都大于自己，就选择较大的。

    最大堆有两个核心操作，一个是上浮，一个是下沉，分别对应 push 和 pop。

    这是一个最大堆：

    用数组表示为：[11 5 8 3 4]

    1.2. 上浮操作

    我们要往堆里 push 一个元素 15，我们先把 X = 15 放到树最尾部，然后进行上浮操作。

    因为 15 大于其父亲节点 8，所以与父亲替换：

    优先队列及堆排序 - 图2

    这时 15 还是大于其父亲节点 11，继续替换：

    操作一次 push 的最好时间复杂度为：O(1)，因为第一次上浮时如果不大于父亲，那么就结束了。最坏的时间复杂度为： O(logn)，相当于每次都大于父亲，会一直往上浮到根节点，翻转次数等于树的高度，而树的高度等于元素个数的对数：log(n)。

    我们现在要将堆顶的元素 pop 出。如图我们要移除最大的元素 11：

    我们先将根节点移除，然后将最尾部的节点 4 放在根节点上：

    优先队列及堆排序 - 图5

    接着对根节点 4 进行下沉操作，与其两个儿子节点比较，发现较大的儿子节点 8 比 4 大，那么根节点 4 与其儿子节点 8 交换位置，向下翻转：

    这样一直向下翻转就维持了最大堆的特征。

    操作一次 pop 最好的时间复杂度也是：O(1)，因为第一次比较时根节点就是最大的。最坏时间复杂度仍然是树的高度：O(logn)。

    1.4. 时间复杂度分析

    构建一个最大堆，从空堆开始，每次添加元素到尾部后，需要向上翻转，最坏翻转次数是：

    从一个最大堆，逐一移除堆顶元素，然后将堆尾元素置于堆顶后，向下翻转恢复堆特征，最坏翻转次数是:

    1. 第一次移除元素恢复堆时间复杂度：logn
    2. 第二次移除元素恢复堆时间复杂度：不大于log(n-1)的最大整数
    3. 第三次移除元素恢复堆时间复杂度：不大于log(n-2)的最大整数
    4. ...
    5. 第N次移除元素恢复堆时间复杂度：log1
    7. 近似 = log(1)+log(2)+log(3)+...+log(n) = log(n!)

    根据斯特林公式：

    优先队列及堆排序 - 图7

    可以进行证明 log(n!) 和 nlog(n) 是同阶的：

    所以构建一个最大堆的最坏时间复杂度是：O(nlogn)。

    从堆顶一个个移除元素，直到移完，整个过程最坏时间复杂度也是：O(nlogn)。

    从构建堆到移除堆，总的最坏复杂度是：O(nlogn)+O(nlogn)，我们可以认为是：O(nlogn)。

    如果所有的元素都一样的情况下，建堆和移除堆的每一步都不需要翻转，最好时间复杂度为：O(n)，复杂度主要在于遍历元素。

    如果元素不全一样，即使在建堆的时候不需要翻转，但在移除堆的过程中一定会破坏堆的特征，导致恢复堆时需要翻转。比如一个 n 个元素的已排好的序的数列，建堆时每次都满足堆的特征，不需要上浮翻转，但在移除堆的过程中最尾部元素需要放在根节点，这个时候导致不满足堆的特征，需要下沉翻转。因此，在最好情况下，时间复杂度仍然是：O(nlog)。

    因此，最大堆从构建到移除，总的平均时间复杂度是：O(nlogn)。

    1.5. 最大堆实现

    以上为最大堆的实现。

    先构建一个最小堆，然后依次把根节点元素 pop 出即可：

    1. func main() {
    4.     // 构建最大堆
    5.     h := NewHeap(list)
    6.     for _, v := range list {
    7.         h.Push(v)
    8.     }
    10.     // 将堆元素移除
    11.     for range list {
    12.         h.Pop()
    13.     }
    14.     // 打印排序后的值
    15.     fmt.Println(list)
    16. }

    输出：

    根据以上最大堆的时间复杂度分析，从堆构建到移除最坏和最好的时间复杂度：O(nlogn)，这也是堆排序的最好和最坏的时间复杂度。

    这样实现的堆排序是普通的堆排序，性能不是最优的。

    因为一开始会认为堆是空的，每次添加元素都需要添加到尾部，然后向上翻转，需要用 Heap.Size 来记录堆的大小增长，这种堆构建，可以认为是非原地的构建，影响了效率。

    美国籍计算机科学家 R. W. Floyd 改进的原地自底向上的堆排序，不会从空堆开始，而是把待排序的数列当成一个混乱的最大堆，从底层逐层开始，对元素进行下沉操作，一直恢复最大堆的特征，直到根节点。

    将构建堆的时间复杂度从 O(nlogn) 降为 O(n)，总的堆排序时间复杂度从 O(2nlogn) 改进到 O(n+nlogn)。

    三、自底向上堆排序

    自底向上堆排序，仅仅将构建堆的时间复杂度从 O(nlogn) 改进到 O(n)，其他保持不变。

    这种堆排序，不再每次都将元素添加到尾部，然后上浮翻转，而是在混乱堆的基础上，从底部向上逐层进行下沉操作，下沉操作比较的次数会减少。步骤如下：

    1. 先对最底部的所有非叶子节点进行下沉，即这些非叶子节点与它们的儿子节点比较，较大的儿子和父亲交换位置。
    2. 接着从次二层开始的非叶子节点重复这个操作，直到到达根节点最大堆就构建好了。

    从底部开始，向上推进，所以这种堆排序又叫自底向上的堆排序。

    为什么自底向上构建堆的时间复杂度是：O(n)。证明如下：

    第 k 层的非叶子节点的数量为 n/2^k，每一个非叶子节点下沉的最大次数为其子孙的层数：k，而树的层数为 logn 层，那么总的翻转次数计算如下：

    优先队列及堆排序 - 图9

    因为如下的公式是成立的：

    所以翻转的次数计算结果为：2n 次。也就是构建堆的时间复杂度为：O(n)。

    我们用非递归的形式来实现，非递归相对容易理解：

    1. package main
    3. import "fmt"
    5. // 先自底向上构建最大堆，再移除堆元素实现堆排序
    6. func HeapSort(array []int) {
    7.     // 堆的元素数量
    8.     count := len(array)
    10.     // 最底层的叶子节点下标，该节点位置不定，但是该叶子节点右边的节点都是叶子节点
    11.     start := count/2 + 1
    13.     // 最后的元素下标
    14.     end := count - 1
    16.     // 从最底层开始，逐一对节点进行下沉
    17.     for start >= 0 {
    19.         start-- // 表示左偏移一个节点，如果该层没有节点了，那么表示到了上一层的最右边
    20.     }
    22.     // 下沉结束了，现在要来排序了
    23.     // 元素大于2个的最大堆才可以移除
    24.     for end > 0 {
    25.         // 将堆顶元素与堆尾元素互换，表示移除最大堆元素
    26.         array[end], array[0] = array[0], array[end]
    27.         // 对堆顶进行下沉操作
    28.         sift(array, 0, end)
    29.         // 一直移除堆顶元素
    30.         end--
    31. }
    33. // 下沉操作，需要下沉的元素时 array[start]，参数 count 只要用来判断是否到底堆底，使得下沉结束
    34. func sift(array []int, start, count int) {
    35.     // 父亲节点
    36.     root := start
    38.     // 左儿子
    39.     child := root*2 + 1
    41.     // 如果有下一代
    42.     for child < count {
    43.         // 右儿子比左儿子大，那么要翻转的儿子改为右儿子
    44.         if count-child > 1 && array[child] < array[child+1] {
    45.             child++
    46.         }
    48.         // 父亲节点比儿子小，那么将父亲和儿子位置交换
    49.         if array[root] < array[child] {
    50.             array[root], array[child] = array[child], array[root]
    51.             // 继续往下沉
    52.             root = child
    53.             child = root*2 + 1
    54.         } else {
    55.             return
    56.         }
    57.     }
    58. }
    60. func main() {
    61.     list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
    63.     HeapSort(list)
    65.     // 打印排序后的值
    66. }

    输出：

    附录

    代码下载： 。