堆排序是我觉得排序里面数据结构运用最灵活的一个算法，首先如何用一个数组表示一个堆，如何取到节点的父节点和左右子节点。

10.png

左侧是一个堆，右侧是一个数组的索引，可见我们只要从上到下，从左到右填充数字，并且保证，所有父节点大于两个子节点就可以构成一个堆。

对于一个堆，我们可以通过父节点和子节点之间的索引总结出如下关系：

// func heap(i int) {
//  parent := (i - 1) / 2   // 父节点
//  c1 := 2*i + 1          // 左子节点
//  c2 := 2*i + 2          // 右子节点
// }

算法描述

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

上代码

// 保证父节点大于两个子节点
func heapify(tree []int, n, i int) {
    if i >= n {
        return
    }
    c1 := 2*i + 1 // 左子节点
    c2 := 2*i + 2 // 右子节点

    max := i // 默认最大节点是当前节点
    if c1 < n && tree[c1] > tree[max] {
        // 最大节点是左节点
        max = c1
    }
    if c2 < n && tree[c2] > tree[max] {
        // 最大节点是右节点
        max = c2
    }

    // 如果最大节点不是当前节点
    if max != i {
        // 交换最大节点和子节点
        tree[max], tree[i] = tree[i], tree[max]
        // 对子节点重新堆化
        heapify(tree, n, max)
    }
}

// 数组建堆
func buildHeap(tree []int, n int) {
    lastNode := n - 1            // 最后一个节点
    parent := (lastNode - 1) / 2 // 最后一个节点的父节点
    for i := parent; i >= 0; i-- {
        heapify(tree, n, i)
    }
}

func heapSort(tree []int, n int) {
    buildHeap(tree, n) // 建堆
    fmt.Println(tree)
    for i := n - 1; i >= 0; i-- {
        // 0 为堆顶元素  必定是最大
        tree[i], tree[0] = tree[0], tree[i]
        heapify(tree, i, 0) // 继续堆化
    }
}

func TestHeapify(t *testing.T) {
    tree := rand.Perm(10)
    t.Log(tree)
    heapSort(tree, len(tree))
    t.Log(tree)
}

小结

堆排序我在理解过程中，很容易犯一个错误，以为通过中序遍历就可以拿到一个有序数组，其实不然，堆只是保证了父节点大于两个子节点，并没有保证子节点之间的一个大小关系，没有保证左子树和右子树的大小关系。

9.png

通过这个例子就很好理解，但是可见根节点是最大元素，根节点比各个子节点，以及子节点的父节点都要大。

参考文档

• Bilibili 堆排序