排序算法 - 堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。

类型：选择排序
时间复杂度（最坏）：O(nlogn)
时间复杂度（最好）：O(nlogn)
时间复杂度（平均）：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定（堆的根元素与最后一个叶节点交换值时会导致不稳定）

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。且完全二叉树可以基于数组存储（父子节点的关系可以用数组下标表示），加持上堆的特性，故可以做堆排序。

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树；即每一层节点数都达到最大值；即深度为 k 的二叉树节点个数为 2^k-1，则为满二叉树。

完全二叉树：若设二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，且第 k 层所有的结点都连续集中在最左边，这就是完全二叉树。

堆：基于完全二叉树，分为大顶堆/小顶堆。各节点的数值皆大于其左右子节点的数值（大顶堆），或各节点的数值皆小于其左右子节点的数值（小顶堆）。

堆的特性

大顶堆，节点的数值皆大于子节点的数值，下文都以大顶堆为实例讲解。

因为是基于完全二叉树的，所以堆还有一些相应的特性：

1、位序为 n 的节点，其父节点位序为 (int) n/2
2、位序为 n 的节点，其左子节点位序为 2n，右子节点位序为 2n+1（这是按照位序从1开始计算，但对编程语言不太友好，如果位序从0开始计算，则左子节点位序为 2n+1, 右子节点位序为 2n+2）

按照数组下标的方式去编号的话如下：

0
             /   \
            1     2
           / \  /  \
         3    4 5   6
              ...
       /
  floor(n/2)  ...
     /  
    n
   / \
2n+1  2n+2

可以发现，所有非叶子节点的序号都会落在 0 ~ (int) N/2-1 区间中，N为节点总数，例如：
1、有4个节点，节点编号为0~3，非叶子节点编号区间值为 0~1，即编号为 0，1 的节点为非叶子节点。
2、有5个节点，节点编号为0~4，非叶子节点编号区间值为 0~1，即编号为 0，1 的节点为非叶子节点。
3、有6个节点，节点编号为0~5，非叶子节点编号区间值为 0~2，即编号为 0，1，2 的节点为非叶子节点。
4、有7个节点，节点编号为0~6，非叶子节点编号区间值为 0~2，即编号为 0，1，2 的节点为非叶子节点。

可以很方便的获取完全二叉树的非叶子节点的序号集合，从 k-1 层开始，依次将各非叶子节点及其左右子节点视为一个完全二叉树，将其调整至大顶堆，直至根节点，这时整个二叉树就是一个大顶堆

我们有了非叶子节点的序号及获取左右节点序号的算式，所以很容易就可以将各非叶子节点及其左右子节点组成的完全二叉树调整至大顶堆。同时要注意如果非叶子节点同其左右子节点发生了调整，其左右子节点如果也是非叶子节点的话，也要检测是否破坏了堆特性，如破坏也需进行调整。

堆排序

堆排序：

• 将初始待排序关键字序列(R0,R1….Rn-1)构建成大顶堆，此堆为初始的无序区
• 将堆顶元素R[0]与最后一个元素R[n-1]交换，此时得到新的无序区(R0,R1,...,Rn-2)和新的有序区(Rn-1),且满足R[1,2…n-2]<=R[n-1]
• 由于交换后新的堆顶R[0]可能违反堆的性质，因此需要对当前无序区(R0,R1,...,Rn-2)调整为新堆，然后再次将R[0]与无序区最后一个元素交换，得到新的无序区(R0,R1….Rn-3)和新的有序区(Rn-2,Rn-1)。不断重复此过程直到有序区的元素个数为n-1（第n-1次调整时完全二叉树只有2个节点，即可有序化），则整个排序过程完成。

即堆排序的过程:将待排序数组映射到完全二叉树中，通过调整完全二叉树至大顶堆，获取根节点的值（节点最大值）。

那大顶堆的构建如何做呢？我用比较白话的方式讲一下

1、从 k 层开始，将每一层子节点的最大值与其父节点的值进行比较调整（如发生交换且子节点为非叶子节点，也要检查子节点的树是否满足了父节点大于子节点的特性）
2、重复第一步骤直到根节点，此时根节点的值即为完全二叉树节点中的最大值，即生成了大顶堆

时间复杂度：O(nlogn)
空间复杂度：O(1)

golang 源码实例

package main

import (
    "fmt"
)

func main() {
    // 待排序数组 go 的数组传参是值拷贝 我们用切片引用传值更方便些
    var arr = []int{1, 6, 2, 4, 5, 3, 7, 9, 8}
    HeapSort(arr)
    fmt.Print("sorted: ", arr)
}

// 堆排序
func HeapSort(arr []int) {
    arrLength := len(arr)
    // 每一次的堆构建都能得到一个节点中的最大值（根节点）对于N个待排序数列，N-1次堆构建即可得出有序数列
    for i := 0; i < arrLength; i++ {
        // 无序区长度
        arrLengthUnsorted := arrLength - i
        // 无序区构建为完全二叉树后非叶节点的下标的范围
        unLeafNodeIndexRange := int(arrLengthUnsorted/2 - 1)
        // 从 k - 1 层开始 将非叶节点的子树分治递归构建成大顶堆
        for j := unLeafNodeIndexRange; j >= 0; j-- {
            HeapBuild(arr, j, arrLengthUnsorted)
        }
         
        // 打印下标 0 ~ arrLengthUnsorted-1 的数列
        fmt.Println("current heap: ", arr[0:arrLengthUnsorted])
        // 一次大顶堆构建完成，根节点为堆最大值，与无序区堆的最后一个节点交换
        // 无序区节点数-1
        // 破坏了堆结构 开始对新无序区做大顶堆构建
        SwapItemOfArray(arr, 0, arrLengthUnsorted-1)
    }
}

// 将子树调整为大顶堆
func HeapBuild(arr []int, nodeIndex int, arrLengthUnsorted int) {
    // 完全二叉树子节点下标同父节点下标的关系式
    leftChildNodeIndex, rightChildNodeIndex := nodeIndex*2+1, nodeIndex*2+2

    // 防止子节点下标越界 && 子节点数值大于父节点 则交换节点值
    if leftChildNodeIndex < arrLengthUnsorted && arr[leftChildNodeIndex] > arr[nodeIndex] {
        SwapItemOfArray(arr, leftChildNodeIndex, nodeIndex)
        HeapBuild(arr, leftChildNodeIndex, arrLengthUnsorted) //左子树根节点改变 需调整堆结构
    }

    if rightChildNodeIndex < arrLengthUnsorted && arr[rightChildNodeIndex] > arr[nodeIndex] {
        SwapItemOfArray(arr, rightChildNodeIndex, nodeIndex)
        HeapBuild(arr, rightChildNodeIndex, arrLengthUnsorted) //右子树根节点改变 需调整堆结构
    }

}

// 交换数组两个元素
func SwapItemOfArray(arr []int, indexX int, indexY int) {
    temp := arr[indexX]
    arr[indexX] = arr[indexY]
    arr[indexY] = temp
}

运行过程及结果

current heap: [9 8 7 6 5 2 3 1 4]
current heap: [8 6 7 4 5 2 3 1]
current heap: [7 5 6 1 4 2 3]
current heap: [6 4 5 1 3 2]
current heap: [5 3 4 1 2]
current heap: [4 2 3 1]
current heap: [3 1 2]
current heap: [2 1]
current heap: [1]
sorted: [1 2 3 4 5 6 7 8 9]