000.Go标准库中的堆

堆可以手动实现，也可以使用 go 标准库中提供的堆

go 标准库中的堆

container/heap 包提供了对任意类型（实现了 heap.Interface 接口）的堆操作

heap.Interface 接口

heap.Interface 接口：

type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

sort.Interface 接口：

type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

在实现了这些接口之后，就可以被 heap 包提供的各个函数进行操作，从而实现一个堆。

注意：接口的 Push 和 Pop 方法是供 heap 包调用的，请使用 heap.Push 和 heap.Pop 来向一个堆添加或者删除元素。

成员函数

heap 包中提供了几个最基本的堆操作函数，包括 Init，Push，Pop，Fix 和 Remove （其中 up, down 函数为非导出函数）。这些函数都通过调用前面实现接口里的方法，对堆进行操作。

heap.Init

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

heap.Push

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

heap.Pop

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

heap.Fix

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

heap.Remove

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()
}

heap.down

func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > i0
}

heap.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
	}
}

使用 container/heap

实现所有 5 个接口方法

像这样

实现 sort 包下现成的结构 + 实现 2 个接口方法

像这样