今天来介绍下,golang的一个pkg包,containter/heap,官方实现的heap的操作,包 heap 为所有实现了 heap.Interface 的类型提供堆操作,这里实现的是最小堆。
1. 堆简介:
堆是一棵满二叉树,分为最大堆和最小堆两种,最大堆的指的是左右子树的节点都小于根节点,最小堆则相反,堆一般用于处理topk问题,也可以用于优先级队列。
2. Heap的API介绍:
// 在索引 i 上的元素的值发生变化之后, 重新修复堆的有序性。
// 先修改索引 i 上的元素的值然后再执行 Fix ,
// 跟先调用 Remove(h, i) 然后再使用 Push 操作将新值重新添加到
// 堆里面的做法具有同等的效果, 但前者所需的计算量稍微要少一些。
// Fix 函数的复杂度为 O(log(n)) , 其中 n 等于 h.Len() 。
func Fix(h Interface, i int)
//在执行任何堆操作之前, 必须对堆进行初始化。
// Init 操作对于堆不变性(invariants)具有幂等性,
// 无论堆不变性是否有效, 它都可以被调用。
// Init 函数的复杂度为 O(n) , 其中 n 等于 h.Len() 。
func Init(h Interface)
// Pop 函数根据 Less 的结果, 从堆中移除并返回具有最小值的元素,
// 等同于执行 Remove(h, 0) 。
// Pop 函数的复杂度为 O(log(n)) , 其中 n 等于 h.Len() 。
func Pop(h Interface) interface{}
// Push 函数将值为 x 的元素推入到堆里面,
// 该函数的复杂度为 O(log(n)) , 其中 n 等于 h.Len() 。
func Push(h Interface, x interface{})
// Remove 函数将移除堆中索引为 i 的元素,
// 该函数的复杂度为 O(log(n)) , 其中 n 等于 h.Len() 。
func Remove(h Interface, i int) interface{}
2. Heap的使用:
heap的使用,需要先实现5个函数,Len(),Less(),Swap(),Push(),Pop(),因为heap的API 需要用到这些基本的操作函数。
heap的操作需要实现这5个api的原因是参数为下面的接口,而这个接口需要这5个函数。
例子1: 整数
package main
import (
"container/heap"
"fmt"
)
type IntHeap []int
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{}) {
// Push 和 Pop 使用 pointer receiver 作为参数,
// 因为它们不仅会对切片的内容进行调整,还会修改切片的长度。
*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
}
// 这个示例会将一些整数插入到堆里面, 接着检查堆中的最小值,
// 之后按顺序从堆里面移除各个整数。
func main() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Printf("minimum: %d\n", (*h)[0])
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
}
}
执行结果:
minimum: 1
1 2 3 5
最大堆的实现,只需要将Less()函数修改为下面的情况:
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }// 最大堆
执行结果:
minimum: 5
5 3 2 1
例子2: 数据结构使用堆
package main
import (
"container/heap"
"fmt"
)
type Student struct {
Name string
Grade int
}
type StudentHeap []Student
func (h StudentHeap) Len() int { return len(h) }
func (h StudentHeap) Less(i, j int) bool { return h[i].Grade < h[j].Grade }
func (h StudentHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *StudentHeap) Push(x interface{}) {
*h = append(*h, x.(Student))
}
func (h *StudentHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
// 按照Grade排序的最小堆
func main() {
h := StudentHeap{}
h = append(h, Student{Name: "mingming", Grade: 90})
h = append(h, Student{Name: "xiaoxiao", Grade: 60})
h = append(h, Student{Name: "congcong", Grade: 88})
heap.Init(&h)
heap.Push(&h, Student{Name: "sese", Grade: 78})
for h.Len() > 0 {
fmt.Printf("%v ", heap.Pop(&h))
}
}
执行结果:
{xiaoxiao 60} {sese 78} {congcong 88} {mingming 90}
3.heap的实现
下面是源代码实现,因为担心外网的问题访问不到,是故代码粘贴如下所示,摘自:https://golang.org/src/container/heap/heap.go
package heap
import "sort"
// The Interface type describes the requirements
// for a type using the routines in this package.
// Any type that implements it may be used as a
// min-heap with the following invariants (established after
// Init has been called or if the data is empty or sorted):
//
// !h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
//
// Note that Push and Pop in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use heap.Push and heap.Pop.
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
func Init(h Interface) {
// heapify
n := h.Len()
for i := n/2 - 1; i >= 0; i-- {
down(h, i, n)
}
}
// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x interface{}) {
h.Push(x)
up(h, h.Len()-1)
}
// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h Interface) interface{} {
n := h.Len() - 1
h.Swap(0, n)
down(h, 0, n)
return h.Pop()
}
// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
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 re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
func Fix(h Interface, i int) {
if !down(h, i, h.Len()) {
up(h, i)
}
}
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
}
}
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
}
参考文档:
https://golang.org/src/container/heap/heap.go https://golang.org/pkg/container/heap http://cngolib.com/container-heap.html