文章目录
- 前言
- 堆定义
- 堆分类
- 实现原理
- 代码实现
- 堆排序
- 最后
前言
你好，我是醉墨居士，我们现在开始从零学习堆相关的概念，堆的特点，实现原理，代码实现
堆定义
堆通常是一个可以被看做一棵树的数组对象。它具有以下特点：
堆中某个节点的值总是不大于或不小于其父节点的值。
堆总是一棵完全二叉树。这意味着除了最后一层外，其他层的节点都是满的，并且最后一层的节点从左到右依次排列。
堆分类
大顶堆：在大顶堆中，每个节点的值都大于或等于其子节点的值。根节点的值是堆中的最大值。
小顶堆：在小顶堆中，每个节点的值都小于或等于其子节点的值。根节点的值是堆中的最小值。
实现原理
我们以小顶堆为例，我们使用一个数组来表示堆，数组中每一个元素表示堆对应的完全二叉树节点。数组的0号索引表示堆的根节点，对于索引为i的节点来说，左孩子为数组中索引为2 * i + 1的元素，右孩子为数组中索引为2 * i + 2的元素。父节点为数组中索引为(i - 1) / 2的元素
- 添加元素到堆中
将待插入元素追加到数组的最后，然后从最后一个元素执行上浮（如果当前元素大于父节点元素时触发交换），不断进行上浮，直至最终上浮到堆顶，或者当前元素不小于父元素 - 删除并查看堆顶元素：
第一个元素即为返回的堆顶元素，也就是最小值
将最后一个元素交换到第一个元素，然后淘汰最后一个元素，然后从第一个元素执行下沉（如果当前元素小于 左孩子节点与右孩子节点元素的最小值 时触发交换），不断进行下沉，直至最终当前元素的左孩子或者右孩子不存在，或者当前元素不大于左孩子或右孩子 - 查看堆顶元素
返回数组中索引为0的元素 - 查看堆中元素的长度
返回数组的长度
大顶堆，只需要把上述中上浮或者下沉中比较符号取反即可
代码实现
type Heap[T cmp.Ordered] []Tfunc (h *Heap[T]) Push(val T) {// 将待插入元素追加到数组的最后*h = append(*h, val)// 然后从最后一个元素执行上浮（如果当前元素大于父节点元素时触发交换）idx := len(*h) - 1for idx > 0 {// 不断进行上浮，直至最终上浮到堆顶，或者当前元素不小于父元素parentIdx := (idx - 1) >> 1if (*h)[parentIdx] > (*h)[idx] {(*h)[parentIdx], (*h)[idx] = (*h)[idx], (*h)[parentIdx]idx = parentIdx} else {break}}
}func (h *Heap[T]) Pop() (ans *T){if len(*h) == 0 {return nil}// 第一个元素即为返回的堆顶元素，也就是最小值ans = &(*h)[0]// 将最后一个元素交换到第一个元素(*h)[0] = (*h)[len(*h) - 1]// 淘汰最后一个元素(*h) = (*h)[:len(*h) - 1]// 然后从第一个元素执行下沉（如果当前元素小于 左孩子节点与右孩子节点元素的最小值 时触发交换）idx := 0for idx < len(*h) {// 不断进行下沉，直至最终当前元素的左孩子或者右孩子不存在，或者当前元素不大于左孩子或右孩子l, r := idx << 1 + 1, idx << 1 + 2parentIdx := idxif l < len(*h) && (*h)[l] < (*h)[parentIdx] {parentIdx = l}if r < len(*h) && (*h)[r] < (*h)[parentIdx] {parentIdx = r}if parentIdx == idx {break}(*h)[parentIdx], (*h)[idx] = (*h)[idx], (*h)[parentIdx]idx = parentIdx}return
}func (h *Heap[T]) Peek() *T {if len(*h) == 0 {return nil}// 返回数组中索引为0的元素return &(*h)[0]
}func (h *Heap[T]) Len() int {// 返回数组的长度return len(*h)
}
堆排序
我们只需要将待排序数组的元素加入到小顶堆中，然后依次弹出的元素就是从小到大排列的，反之如果加入的是大顶堆，则是从大到小排序
func HeapSort[T cmp.Ordered](nums *[]T) {he := &Heap[T]{}for _, num := range *nums {he.Push(num)}for i := 0; he.Len() > 0; i++ {(*nums)[i] = *he.Pop()}
}
最后
好的，我们已经了解堆的概念与实现原理编写，希望对你有所帮助，也请你多多点赞、收藏、关注、评论
