0. 概述

在 Go 中,自带的数据结构不多,其中,堆 (heap) 是其中一个,本文就先介绍一下如何使用 Go 语言中的堆,然后看它是怎么实现的。

1. heap 的使用

根据 heap 的官方文档,heap 的使用方式为:

  1. [[email protected].io]# cat heap_sample00.go
  2. heapObj := MinHeap{}
  3. heap.Init(&heapObj)
  4. heap.Push(&heapObj, &Item{Value: 1, Priority: 1})
  5. item := heap.Pop().(*Item)

这里有四个操作,分别是:

这里有一些关键的地方,分别是:

这里先解答第一个问题,这个 Object 要怎么实现,根据 Heap 的文档,要实现的 Interface 为:

  1. [[email protected].io]# cat interface.go
  2. type Interface interface {
  3. sort.Interface
  4. Push(x interface{}) // add x as element Len()
  5. Pop() interface{} // remove and return element Len() - 1.
  6. }

sort.Interface 就很简单了,有三个函数需要实现,分别是:

  1. [[email protected].io]# cat sort.go
  2. type Interface interface {
  3. Len() int
  4. Less(i, j int) bool
  5. Swap(i, j int)
  6. }

Push 方法

Push 方法和 Pop 方法需要着重介绍一下,因为他们有一些隐藏的知识。

如果你是用树组来实现 Heap 的话,那么你需要保证插入的元素是处于最后位的。所以一个简单的实现是这样的:

  1. [[email protected].io]# cat push.go
  2. func (h *MaxHeap) Push(x interface{}) {
  3. *h = append(*h, x.(*Item))
  4. }

Pop 方法

Pop 就有更多的规矩了,首先得保证 Pop 完之后,树组的元素是要少一个的,长度也要减掉,这个是由我们自己来实现的;然后,需要注意的是,heap 包已经帮我们把要移除的元素放在了最后,所以,只需要把最后一个元素返回去就可以了。

一个示例为:

  1. [[email protected].io]# cat pop.h
  2. func (h *MinHeap) Pop() interface{} {
  3. x := (*h)[len(*h)-1]
  4. *h = (*h)[0 : len(*h)-1]
  5. return x
  6. }

2. heap 的实现

可能让你实现这个 Interface 你会觉得很不习惯,因为不理解为什么 heap 要这么做,所以,一个最好的方式还是结合 heap 的源码来看一下才更好一些。

2.1 init 函数

首先,先来看下 Heap 的 Init 做了什么事情:

  1. [[email protected].io]# cat init.go
  2. func Init(h Interface) {
  3. // heapify
  4. n := h.Len()
  5. for i := n/2 - 1; i >= 0; i-- {
  6. down(h, i, n)
  7. }
  8. }

2.2 down 函数

可以看到,这里从 (n / 2 - 1) -> 0 ,每个位置都调用一下 down,那么先看这个 down 函数是什么,再理解一下这个含义:

  1. [[email protected].io]# cat down.go
  2. func down(h Interface, i0, n int) bool {
  3. i := i0
  4. for {
  5. j1 := 2*i + 1
  6. if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
  7. break
  8. }
  9. j := j1 // left child
  10. if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
  11. j = j2 // = 2*i + 2 // right child
  12. }
  13. if !h.Less(j, i) {
  14. break
  15. }
  16. h.Swap(i, j)
  17. i = j
  18. }
  19. return i > i0
  20. }

可以看到,所谓的 down,其实就是不断得找当前节点的子节点,然后比较是否比子节点小,如果是,那么就和子节点交换位置,否则,结束。

那么这有什么意思?很明显,其实是一个递归的思想,所谓堆,只要根节点是最小的就可以了,那么,从叶子节点开始,如果每个父节点都比子节点小,那么不就保证了根节点是最小的了么?用数学公式表达为:

i4 < i8
i2 < i4
i1 < i2
i0 < i1

即可推导出

i0 < i1 < i2 < i4 < i8

所以 i0 即是最小的。

2.3 Push

在前面使用的描述中说到了往 heap 中插入一个元素,其实就是需要把他放到树组的最后面,然后交给标准库就完成,那么,其实标准库要完成的工作就很明确了,就是如何保证这个元素插入后,heap 依旧保持特性。

这里的标准库操作很简单那,两行代码:

  1. [[email protected].io]# cat push.go
  2. // Push pushes the element x onto the heap.
  3. // The complexity is O(log n) where n = h.Len().
  4. func Push(h Interface, x interface{}) {
  5. h.Push(x)
  6. up(h, h.Len()-1)
  7. }

所以这里的关键还是 up 函数。

2.4 up

up 函数和 down 函数相对,down 是将一个元素不断得与自己子节点对比,从而实现父节点肯定比子节点小;而 up 函数则反过来,不断得将子节点与父节点对比,从而保证子节点比父节点大,代码为:

  1. [[email protected].io]# cat up.go
  2. func up(h Interface, j int) {
  3. for {
  4. i := (j - 1) / 2 // parent
  5. if i == j || !h.Less(j, i) {
  6. break
  7. }
  8. h.Swap(i, j)
  9. j = i
  10. }
  11. }

2.5 Pop 函数

那么怎么删除一个元素呢?确定一个删除的元素非常简单,就是树组的第一个元素就是要删除的元素了,那么,删除掉这个元素之后该如何保证 heap 的有效性呢?

删除掉元素之后,其实问题就在于根结点是空的,如果用子节点来补,那么子节点又空了,如果一直补下去,那么很容易造成 heap 的有效性丢失,即不再是一个完全二叉树。例如,可能是这么一种情况:

图 1:错误的删除方法导致堆变性

一个比较好的删除策略就是,删除一个元素之后,将最后一个元素补上来,然后再执行 down 操作,这样,就保证了这是一棵完全二叉树:

图 2:堆的正确删除姿势

可以看出,堆的删除复杂度是 log2n

3. 小结

从前边的分析可以看出,堆只需要保证偏序即可(即只需要保证父节点和子节点之间的顺序,而不需要考虑兄弟节点之间的顺序),这提高了排序的速度,所以有一种排序算法叫做堆排序,他的时间复杂度是 Nlog2N,其实就是一个 init 再加上 N 个 Pop 操作,其中:

额外补充一个: