开篇

在 Golang 的标准库 container 中，包含了几种常见的数据结构的实现，其实是非常好的学习材料，我们可以从中回顾一下经典的数据结构，看看 Golang 的官方团队是如何思考的。

  • container/list 双向链表；
  • container/ring 循环链表；
  • container/heap 堆。

今天我们就来看看 container/heap 的源码，了解一下官方的同学是怎么设计，我们作为开发者又该如何使用。

container/heap

包 heap 为所有实现了 heap.Interface 的类型提供堆操作。 一个堆即是一棵树， 这棵树的每个节点的值都比它的子节点的值要小， 而整棵树最小的值位于树根（root）， 也即是索引 0 的位置上。

堆是实现优先队列的一种常见方法。 为了构建优先队列， 用户在实现堆接口时， 需要让 Less() 方法返回逆序的结果， 这样就可以在使用 Push 添加元素的同时， 通过 Pop 移除队列中优先级最高的元素了。

heap 是实现优先队列的常见方式。Golang 中的 heap 是最小堆，需要满足两个特点：

  • 堆中某个结点的值总是不小于其父结点的值；
  • 堆总是一棵完全二叉树。

所以，根节点就是 heap 中最小的值。

有一个很有意思的现象，大家知道，Golang 此前是没有泛型的，作为一个强类型的语言，要实现通用的写法一般会采用【代码生成】或者【反射】。

而作为官方包，Golang 希望提供给大家一种简单的接入方式，官方提供好算法的内核，大家接入就 ok。采用的是定义一个接口，开发者来实现的方式。

在 container/heap 包中，我们一上来就能找到这个 Interface 定义：

除了 Push 和 Pop 两个堆自己的方法外，还内置了一个 sort.Interface：

核心函数

Init

作为开发者，我们基于自己的结构体，实现了 container/heap.Interface，该怎么用呢？

heap.Init(h Interface)

在执行任何堆操作之前， 必须对堆进行初始化。 Init 操作对于堆不变性（invariants）具有幂等性， 无论堆不变性是否有效， 它都可以被调用。

Init 函数的复杂度为 O(n) ， 其中 n 等于 h.Len() 。

Pop/Push

作为堆，当然需要实现【插入】和【弹出】这两个能力，这里 any 其实就是 interface{}

  • Push 函数将值为 x 的元素推入到堆里面，该函数的复杂度为 O(log(n)) 。
  • Pop 函数根据 Less 的结果， 从堆中移除并返回具有最小值的元素， 等同于执行 Remove(h, 0)，复杂度为 O(log(n))。（n 等于 h.Len() ）

Remove

Remove 函数移除堆中索引为 i 的元素，复杂度为 O(log(n))

Fix

有时候我们改变了堆上的元素，需要重新排序。这时候就可以用 Fix 来完成。

这里需要注意：

  • 【先修改索引 i 上的元素的值然后再执行 Fix】
  • 【先调用 Remove(h, i) 然后再使用 Push 操作将新值重新添加到堆里面】

二者具有同等的效果。但 Fix 的成本会小一些。复杂度为 O(log(n))。

如何接入

将自定义结构实现上面的 heap.Interface 接口后，先进行 Init，随后调用上面我们提到的 Push / Pop / Remove / Fix 即可。其实大多数情况下用前两个就足够了，我们直接看两个例子。

IntHeap

先来看一个简单例子，基于整型 integer 实现一个最小堆。

type IntHeap []int

有了实现，我们 Init 后就可以 Push 进去元素了，这里我们初始化 2,1,5，又 push 了个 3，最后打印结果完美按照从小到大输出。

优先队列

官方也给出了实现优先队列的方法，我们需要一个 priority 作为权值，加上 value。

  • Value 表示元素值
  • Priority 用于排序
  • Index 元素在对上的索引值，用于更新元素的操作。

按时间戳排序

这里我们封装了一个 TimeSortedQueue，里面包含一个时间戳，以及我们实际的值。实现之后，就可以暴露对外的 NewTimeSortedQueue 方法用来初始化，这里调用 heap.Init。

同时做一层简单的封装就可以对外使用了。

总结

Go语言中heap的实现采用了一种 “模板设计模式”，用户实现自定义堆时，只需要实现heap.Interface接口中的函数，然后应用heap.Push、heap.Pop等方法就能够实现想要的功能，堆管理方法是由Go实现好的，存放在heap中。