“如何建立小根堆“初始小根堆的建立

堆是常用的数据结构。堆是完整的二叉树。下图是一个小根堆。小根堆是指树内所有节点的父节点比任何子节点都小。今天我们来看一下如何在Go中实现堆。

以下是在Go语言中实现堆的代码。每个堆需要实施五种方法。这比Java的优先级队列复杂得多。每个Len用于计算容器的长度，Less返回两个元素的大小关系和Swap。

这几个实际上都是用来实现sort接口的。接下来，我们需要实现Push跟Pop方法，对于一个以前不是写Go语言的人，可能觉得这个实现其实很冗余，Push方法我们要做的就是往数据结构的最后面插入一个元素，而Pop则是弹出一个元素，弹出元素则是简单的把最后一个元素取出来。小根堆不是最前面的元素才是最小的么？为什么是取最后一个元素？

我们看一下go语言中，heap的源码，堆需要你实现Push跟Pop接口，因为继承了sort接口，所以又要实现上面3个比较方法。

下面则是sort的接口，要求你实现长度，小于跟交换。

接下来则是堆里面的push操作，先是调用了你实现的往末尾添加一个元素的接口，然后执行up操作，维护小根堆。up操作的目的是为了保证小根堆里面每一个结点都比子节点小。

刚刚我们提出一个疑问，小根堆不是最前面的元素才最小么？这里堆里面的Pop方法是先把最小的元素放到最后面，然后再来维护这个长度减一的小根堆。所以实际上你上面执行方法的时候，最后一个元素才是最小的！

这里不由感叹，还是Java的PriorityQueue封装的好，使用起来更加方便。虽然很多人特别推崇Go，但我觉得每种语言都有各自的优点缺点，都说Go写起来很方便，这不，还是Java大法好。

今天的介绍我们就讲到这里，如果你有兴趣，欢迎关注我，除了分享算法相关的，最近主要会讲一些redis的原理与应用。近期还准备了一些AI相关的知识，整理后会和大家继续分享。大家的支持是我继续唠嗑的动力。同名公众号（沙茶敏碎碎念）