堆排序-构建最大堆

[yankewei]

堆排序

上一节讲了如何从数组完全二叉树，了解了数组和完全二叉树之间的关系，以及完全二叉树的一些特性，这节就讲如何构建一个最大堆。

最大堆

最大堆是一个完全二叉树，所以它自然有完全二叉树的特点，并且节点的值比左右子树的值要大，表达式 node.Val > node.Left.Val && node.Val > node.Right.Val。

如何构建最大堆

所以我们要从完全二叉树构建一个最大堆，就要对非叶子节点进行以下调整。

如果左节点的值大于节点值 node.Val < node.Left.Val，则进行交换。
如果右节点的值大于节点值 node.Val < node.Right.Val， 则进行交换。
交换两次之后，节点值就比左右子树的值都要大，这就是一个最简单的大堆。

依次对每个非叶子节点进行调整，直到根节点，那么最后就可以生成一个最大堆。这里有两个问题：

1. 为什么要从非叶子节点开始？
   因为叶子节点没有子树，所以不需要进行调整。
2. 从哪个非叶子节点开始？
   为了可以对每个非叶子节点进行调整，我们需要从最后一个非叶子节点开始。一个完全二叉树的最后非叶子节点对应的数组索引就是 length/2。注意这里说的索引是从1开始的。比如有数组如下arr [3,2,1,5,6,4]，那么最后一个非叶子节点就是 2。

用一个图来表示整个从完全二叉树到最大堆的过程

最终的代码：

func main() {
    fmt.Println(buildMaxHeap([]int{3, 2, 1, 5, 6, 4})) // 6
}

func buildMaxHeap(slice []int) []int {
    // 这里做一个合并，是为了在数组的第一个元素放置一个元素，这样方便我们后边的计算
    newSlice := append([]int{-1}, slice...)
    for i := (len(newSlice) - 1) / 2; i >= 1; i-- {
	ajustHeap(newSlice, len(newSlice)-1, i)
    }
    return newSlice
}

/**
 * length 是为了我们方便的判断计算的索引值有没有超过长度，避免数组越界
 * index 就是我们要调整的节点
 */
func ajustHeap(slice []int, length int, index int) {
    target := index
    // 计算左节点和右节点的索引值
    leftIndex, rightIndex := index*2, index*2+1
    // 避免数组越界
    if leftIndex <= length && slice[leftIndex] > slice[target] {
	target = leftIndex
    }
    if rightIndex <= length && slice[rightIndex] > slice[target] {
	target = rightIndex
    }
    if target != index {
	slice[index], slice[target] = slice[target], slice[index]
	// 这里要进行递归，上边的图片也展示了这个递归的过程
	ajustHeap(slice, length, target)
    }
    return
}