Go基础：heap的介绍与使用

介绍

堆是一棵树，其特点是每个节点都是其子树中的最小值节点。

树中最小的元素是根，索引为0。

包heap为实现heap.Interface接口的任何类型提供堆操作。

核心接口

heap.Interface

Interface类型描述使用此包中例程的类型要求。

type Interface interface {
        sort.Interface
        Push(x interface{}) // 将x添加至元素Len()的位置
        Pop() interface{}   // 移除并且返回元素Len()-1
}
复制代码

实现它的任何类型都可以用作具有以下不变量的最小堆（在调用Init()后或数据为空或排序时建立）。

注意，这个接口中的Push()和Pop()是由包堆的实现调用的。要从堆中添加和删除内容，请使用heap.Push()和heap.Pop()。

sort.Interface

在heap.Interface中包含了sort.Interface。

type Interface interface {
        Len() int	// Len是集合中的元素个数。
        Less(i, j int) bool
        Swap(i, j int) // Swap交换索引i和索引j的元素
}
复制代码

任意实现了sort.Interface接口的结构体，均可以被sort包下的各种方法进行排序。这些方法通过整数索引来引用基础集合的元素。

Len()和Swap()见上面代码中的注释，现在详细的说说Less()函数。

Less()函数用来判断索引i的元素是否小于索引j的。

如果Less(i, j)和Less(j, i)均返回false，那么认为这两个索引对应的元素相等。

Sort在最终结果中按任意顺序放置相等的元素，而Stable(稳定排序)保留相等元素的原始输入顺序。

Less()函数必须具有传递性：

• 若Less(i, j)和Less(j, k)均为true，则Less(i, k)也为true
• 若Less(i, j)和Less(j, k)均为false，则Less(i, k)也为false

请注意，当涉及非数字（NaN）值时，浮点比较（float32或float64值上的<运算符）不具有传递性。

有关浮点值的正确实现，请参见Float64Slice.Less()。

初始化

Init()函数建立此包中其他例程所需的堆不变量。

Init()对于堆不变量是幂等的(可被多次调用)，并且可以在堆不变量失效时调用。

Init()的时间复杂度是O(n)，n为堆中的元素个数。

func Init(h Interface) {
        // heapify
        n := h.Len()
        for i := n/2 - 1; i >= 0; i-- {
                down(h, i, n)
        }
}
复制代码

就像在数据结构中学过的一样，初始化一个数组堆的方法就是从数组的中间往前，对每个元素进行一次下沉的操作。

操作堆

• Push()：插入元素。
• Pop()：移除并返回堆顶元素。
• Remove()：移除并返回第i个元素。
• Fix()：修复堆。

Push()

Push()将元素x插入到堆中。

Push()的时间复杂度是O(log n)，n为堆中的元素个数。

func Push(h Interface, x interface{}) {
        h.Push(x)
        up(h, h.Len()-1)
}
复制代码

从源码可以看出，实际的插入步骤是先调用heap.Interface接口的Push()函数将待插入的元素x放到堆中的最后一个位置，然后对其进行上浮操作。

Pop()

Pop()从堆中移除并返回最小元素（根据Less）。也就是堆顶元素。

Pop()的时间复杂度是O(log n)，n为堆中的元素个数。

Pop()等价于Remove(h, 0)。

func Pop(h Interface) interface{} {
        n := h.Len() - 1
        h.Swap(0, n)
        down(h, 0, n)
        return h.Pop()
}
复制代码

从源码可以看出，实际的弹出步骤是将第一个元素与最后一个元素进行互换，然后对一个元素进行下沉，最后移除并返回最后一个元素。

Remove

Remove()从堆中移除并返回第i个元素。

Remove()的时间复杂度是O(log n)，n为堆中的元素个数。

func Remove(h Interface, i int) interface{} {
        n := h.Len() - 1
        if n != i {
                h.Swap(i, n)
                if !down(h, i, n) {
			up(h, i)
                }
        }
        return h.Pop()
}
复制代码

Fix()

Fix()在第i个元素的值改变后重新建立堆排序。

更改第i个元素的值，然后调用Fix()相当于调用Remove(h, i)，然后再插入新值，但成本比调用Remove(h, i)低。

Fix()的时间复杂度为O(log n)，n为堆中的元素个数。

func Fix(h Interface, i int) {
        if !down(h, i, h.Len()) {
                up(h, i)
        }
}
复制代码

上浮和下沉

上浮和下沉都是未导出函数。

up()

func up(h Interface, j int) {
        for {
                i := (j - 1) / 2 // parent
                if i == j || !h.Less(j, i) {
                        break
                }
                h.Swap(i, j)
                j = i
            }
}
复制代码

down()

有一个bool类型的返回值，用于表示是否进行了下沉的操作。

func down(h Interface, i0, n int) bool {
        i := i0
        for {
                j1 := 2*i + 1
                if j1 >= n || j1 < 0 { // 上溢出时会导致 j1 < 0
                        break
                }
                j := j1 // 左节点
                if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
                        j = j2 // = 2*i + 2  // 右节点
                }
                if !h.Less(j, i) {
                        break
                }
                h.Swap(i, j)
                i = j
        }
        return i > i0
}
复制代码

使用

以一个int类型的堆来举例，在使用堆之前，我们需要定义堆的底层数组：

type IntHeap []int
复制代码

然后，我们需要实现heap.Interface接口的五个函数：

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
        *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
        old := *h
        n := len(old)
        x := old[n-1]
        *h = old[0 : n-1]
        return x
}
复制代码

需要注意的是，在实现Push()和Pop()的时候，需要使用指针接收，而不能简单的使用对象。因为Go语言结构体传参默认是传值，而在修改切片长度的时候有可能导致切片的引用发生改变，所以需要使用指针接收。

然后，我们就可以使用这个堆了：

func Example_intHeap() {
        h := &IntHeap{2, 1, 5}
        heap.Init(h)
        heap.Push(h, 3)
        fmt.Printf("堆顶元素: %d\n", (*h)[0])
        for h.Len() > 0 {
                fmt.Printf("%d ", heap.Pop(h))
        }
    
        // 输出:
        // 堆顶元素: 1
        // 1 2 3 5
}
复制代码