heap的实现使用到了小根堆，下面先对堆做个简单声明：
1.堆概念
堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。
最大堆和最小堆是二叉堆的两种形式。
最大堆: 根节点的键值是所有堆节点键值中的最大者。
最小堆: 根节点的键值是所有堆节点键值中的最小者。
2.heap
树的最小元素在根部，为index 0.
heap包对任意实现了heap接口的类型提供堆操作。
heap是常用的优先队列的方法，要创建一个优先队列，实现一个具有使用（负的）优先级作为比较的依据的Less方法的Heap接口，如此一来可用Push添加项目而用Pop取出队列最高优先级的项目。
heap需要实现的接口
// Any type that implements heap.Interface 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()
}
// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
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)
}
其中sort.Interface用于排序，heap.Interface中Push和Pop方法分别用于插入和取出元素的操作
heap中的方法
func Fix(h Interface, i int) //在修改第i个元素后，调用本函数修复堆，比删除第i个元素后插入新元素更有效率。复杂度O(log(n))，其中n等于h.Len()。
func Init(h Interface) //初始化一个堆。一个堆在使用任何堆操作之前应先初始化。Init函数对于堆的约束性是幂等的（多次执行无意义），并可能在任何时候堆的约束性被破坏时被调用。本函数复杂度为O(n)，其中n等于h.Len()。
func Pop(h Interface) interface{} //删除并返回堆h中的最小元素（不影响约束性）。复杂度O(log(n))，其中n等于h.Len()。该函数等价于Remove(h, 0)。
func Push(h Interface, x interface{}) //向堆h中插入元素x，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。
func Remove(h Interface, i int) interface{} //删除堆中的第i个元素，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。
4.示例
(1) 存储int类型元素的heap实现
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{}) {
if v,ok := x.(int); ok {
*h = append(*h,v)
}
}
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{5,7,9,2}
heap.Init(h)
heap.Push(h,3)
fmt.Println((*h)[0])
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
}
}
运行结果：（取出的元素是从小到大）
2
2 3 5 7 9
(2) 实现heap的优先队列（以下代码摘自nsq）
type Item struct {
Value interface{}
Priority int64 //优先级
Index int
}
// this is a priority queue as implemented by a min heap
// ie. the 0th element is the *lowest* value
//PriorityQueue实现了heap接口
type PriorityQueue []*Item
func New(capacity int) PriorityQueue {
return make(PriorityQueue, 0, capacity)
}
/*
Len(),Less()和Swap用于按Priority排序
*/
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].Priority < pq[j].Priority
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].Index = i
pq[j].Index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
c := cap(*pq)
if n+1 > c { //扩容
npq := make(PriorityQueue, n, c*2)
copy(npq, *pq)
*pq = npq
}
*pq = (*pq)[0 : n+1]
item := x.(*Item)
item.Index = n
(*pq)[n] = item
}
func (pq *PriorityQueue) Pop() interface{} {
n := len(*pq)
c := cap(*pq)
if n < (c/2) && c > 25 {//缩容
npq := make(PriorityQueue, n, c/2)
copy(npq, *pq)
*pq = npq
}
item := (*pq)[n-1]
item.Index = -1
*pq = (*pq)[0 : n-1]
return item
}
func Test_Pqueue(t *testing.T) {
c := 100
pq := New(c)
for i := 0; i < c+1; i++ {
heap.Push(&pq, &Item{Value: i, Priority: int64(i)})
}
for i := 0; i < c+1; i++ {
item := heap.Pop(&pq)
fmt.Println(item)
}
}
网友评论