[golang] 数据结构-堆排序

接上文 树形选择排序
上篇也说了，树形选择排序相较简单选择排序，虽然减少了时间复杂度，但是使用了较多空间去储存每轮比较的结果，并且每次还要再和胜出节点比较。而堆排序就是为了优化这个问题而在1964年被两位大佬发明。

原理
首先有几个关于树的定义：

如果一棵树每个节点的值都大于（小于）或等于其字节点的话，那么这棵树就是大（小）根树
如果一棵大（小）根树正好又是完全二叉树，则被称为大根堆（小根堆）

堆排序就是利用大根堆（小根堆）的特性进行排序的。
从小到大排序一般用大根堆，从大到小一般用小根堆。

流程

• 先把待排序的数组8、4、12、7、35、9、22、41、2用完全二叉树表示
  

• 按大根堆的特性把这个完全二叉树从最后一个非叶子节点开始比较，把较大值交换到当前位置。遇到上层节点顺序影响下层节点不满足大根堆特性时，再对下层节点进行排序。最终得到初始状态的大根堆。
  
  

• 然后将根节点与最后一个叶子节点进行交换
  

• 交换后，忽略最后一个叶子节点，再对这棵树的节点进行比较与交换，再次得到符合大根堆要求的树。然后继续将根节点与最后的叶子节点进行交换
  

• 以此类推，最终可以得到一个有序的数组
  

复杂度
平均o(n*logn)
由于初次构建大根堆时有较多次的排序，所以不适合对少量元素进行排序。由于相同数值的节点在比较过程中不能保证顺序，所以是种不稳定的排序方法。

代码

package main

import (
    "fmt"
    "math/rand"
)

func main() {
    var length = 20
    var tree []int

    for i := 0; i < length; i++ {
        tree = append(tree, int(rand.Intn(1000)))
    }
    fmt.Println(tree)

    // 此时的切片o可以理解为初始状态二叉树的数(qie)组(pian)表示，然后需要将这个乱序的树调整为大根堆的状态
    // 由于是从树的右下角第一个非叶子节点开始从右向左从下往上进行比较，所以可以知道是从n/2-1这个位置的节点开始算
    for i := length/2 - 1; i >= 0; i-- {
        nodeSort(tree, i, length-1)
    }

    // 次数tree已经是个大根堆了。只需每次交换根节点和最后一个节点，并减少一个比较范围。再进行一轮比较
    for i := length - 1; i > 0; i-- {
        // 如果只剩根节点和左孩子节点，就可以提前结束了
        if i == 1 && tree[0] <= tree[i] {
            break
        }
        // 交换根节点和比较范围内最后一个节点的数值
        tree[0], tree[i] = tree[i], tree[0]
        // 这里递归的把较大值一层层提上来
        nodeSort(tree, 0, i -1)
        fmt.Println(tree)
    }
}

func nodeSort(tree []int, startNode, latestNode int) {
    var largerChild int
    leftChild := startNode*2 + 1
    rightChild := leftChild + 1

    // 子节点超过比较范围就跳出递归
    if leftChild >= latestNode {
        return
    }

    // 左右孩子节点中找到较大的，右孩子不能超出比较的范围
    if rightChild <= latestNode && tree[rightChild] > tree[leftChild] {
        largerChild = rightChild
    } else {
        largerChild = leftChild
    }

    // 此时startNode节点数值已经最大了，就不用再比下去了
    if tree[largerChild] <= tree[startNode] {
        return
    }

    // 到这里发现孩子节点数值比父节点大，所以交换位置，并继续比较子孙节点，直到把大鱼捞上来
    tree[startNode], tree[largerChild] = tree[largerChild], tree[startNode]
    nodeSort(tree, largerChild, latestNode)
}

注：代码里用递归并不是最优解

运行结果