图文堆排序
曦子图文理解堆排序.
缘起
堆排序咋一看有点反直觉, 这里详细记录下算法过程。
了解几个概念
- 完全二叉树
- 大堆/小堆
大堆就是父结点大于等于其子结点的值.
思路
考虑有个数组 [2, 1, 3] 我们想降序排列也就是变成 [3, 2, 1]。
我们先用完全二叉树的形式他构建成大堆, 如下:
很简单, 用代码也能简单的实现, 下面介绍下一个概念 heapify, 简单来说就是让三个结点最大的在父节点.
如何排序呢, 我们把最后的叶子结点 2 和root结点 3 交换, 然后最大值就在最后的叶子结点, 把最后一个节点摘掉, 那么取到了当前最大值, 但是当前的堆可能是乱掉的, 那么我们再次执行 heapify, 然后移除最后的叶子结点, 如此反复即可.
细节
了解了大致原理, 我们再来深入到细节。
heapify 函数
假设我们有一个数组[6, 7, 3, 2, 1, 9, 8, 5], 构造成二叉树.
从图上我们可以看出, 当我们拿到数组的 index 可以轻松计算出其父结点和子结点.
heapify 函数也很简单, 如下:
func heapify(nums []int, n int, i int) {
largest := i
l := 2*i + 1
r := 2*i + 2
if l < n && nums[l] > nums[largest] {
largest = l
}
if r < n && nums[r] > nums[largest] {
largest = r
}
if largest != i {
nums[i], nums[largest] = nums[largest], nums[i]
// 对子结点进行调整
heapify(nums, n, largest)
}
}构建大堆
在一个简单的二叉树(只有三个结点的时候)构建成大堆我们已经处理过了, 怎么让一个复杂的二叉树构建成大堆呢？
逻辑上很简单, 我们只要从最后一个叶子结点的父结点往根结点方向一直执行 heapify 即可.
最后一个叶子结点的下标是 n-1, 那么根据上述公式其父节点为 即 - 1.
func heapSort(nums []int) {
n := len(nums)
for i := n/2 - 1; i >= 0; i-- {
heapify(nums, n, i)
}
}执行后数组从 [6, 7, 3, 2, 1, 9, 8, 5] 变为 [9 7 8 5 1 3 6 2].
final
上面我们成功构建了大堆, 那么现在我们只有每构建成大堆, 把root结点跟最后的叶子结点交换, 移除叶子结点(取出最大值), 然后再对剩下的元素进行heapify, 继续取最大值, 反复操作即可.
func heapSort(nums []int) {
n := len(nums)
for i := n/2 - 1; i >= 0; i-- {
heapify(nums, n, i)
}
for i := n - 1; i >= 0; i-- {
nums[0], nums[i] = nums[i], nums[0]
heapify(nums, i, 0)
}
}总结
堆排序很容易忘记, 详细记一下.