当i=0时,Remove 就是 Pop
// 弹出堆顶的元素,并返回其值 func (h *Heap) Pop() int { n := len(*h) - 1 h.swap(0, n) x := (*h)[n] *h = (*h)[0:n] h.down(0) return x } 初始化-Init在我们讲完了堆的核心操作 up 和 down 后,我们来讲如何根据一个数组构造一个最小堆。
其实我们可以写个循环,然后将各个元素依次 push 进去,但是这次我们利用数学规律,直接由一个数组构造最小堆。
首先,将所有关键码放到一维数组中,此时形成的完全二叉树并不具备最小堆的特征,但是仅包含叶子结点的子树已经是堆。
即在有n个结点的完全二叉树中,当 i>n/2-1 时,以i结点为根的子树已经是堆。
func (h Heap) Init() { n := len(h) // i > n/2-1 的结点为叶子结点本身已经是堆了 for i := n/2 - 1; i >= 0; i-- { h.down(i) } } 测试 func main() { var h = heap.Heap{20, 7, 3, 10, 15, 25, 30, 17, 19} h.Init() fmt.Println(h) // [3 7 20 10 15 25 30 17 19] h.Push(6) fmt.Println(h) // [3 6 20 10 7 25 30 17 19 15] x, ok := h.Remove(5) fmt.Println(x, ok, h) // 25 true [3 6 15 10 7 20 30 17 19] y, ok := h.Remove(1) fmt.Println(y, ok, h) // 6 true [3 7 15 10 19 20 30 17] z := h.Pop() fmt.Println(z, h) // 3 [7 10 15 17 19 20 30] } 完整代码Github
堆排序在讲完堆的基础知识后,我们再来看堆排序就变得非常简单。利用最小堆的特性,我们每次都从堆顶弹出一个元素(这个元素就是当前堆中的最小值),即可实现升序排序。代码如下:
// 堆排序 var res []int for len(h) != 0 { res = append(res, h.Pop()) } fmt.Println(res) 优先队列优先队列是0个或者多个元素的集合,每个元素都有一个关键码,执行的操作有查找,插入和删除等。
优先队列的主要特点是支持从一个集合中快速地查找并移出具有最大值或最小值的元素。
堆是一种很好的优先队列的实现方法。
参考资料《数据结构与算法》张铭 王腾蛟 赵海燕 编著
GO SDK 1.13.1 /src/container/heap
最后本文是自己的学习笔记,在刷了几道LeetCode中关于堆的题目后,感觉应该系统的学习和总结一下这一重要的数据结构了。
强烈建议看Go的源码中关于heap的实现,仔细感受面向接口编程的思想,和他们的代码风格以及质量。