Golang中container/heap包用法
文章目录
heap包对任意实现了heap接口的类型提供堆操作。(小根)堆是具有“每个节点都是以其为根的子树中最小值”属性的树。树的最小元素在根部,为index 0.
heap是常用的实现优先队列的方法。要创建一个优先队列,实现一个具有使用(负的)优先级作为比较的依据的Less方法的Heap接口,如此一来可用Push添加项目而用Pop取出队列最高优先级的项目。
1 | type Interface |
可以看出,这个堆结构继承自sort.Interface, 而sort.Interface,需要实现三个方法:
1 | Len() int / Less(i, j int) bool / Swap(i, j int) |
再加上堆接口定义的两个方法:
1 | Push(x interface{}) / Pop() interface{}。 |
故只要实现了这五个方法,变定义了一个堆。
任何实现了本接口的类型都可以用于构建最小堆。最小堆可以通过heap.Init建立,数据是递增顺序或者空的话也是最小堆。最小堆的约束条件是:
1 | !h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len() |
注意接口的Push和Pop方法是供heap包调用的,请使用heap.Push和heap.Pop来向一个堆添加或者删除元素。
1 | func Fix(h Interface, i int) // 在修改第i个元素后,调用本函数修复堆,比删除第i个元素后插入新元素更有效率。复杂度O(log(n)),其中n等于h.Len()。 |
举例说明其用法:
1 | package main |
利用heap创建一个优先级队列
1 | // This example demonstrates a priority queue built using the heap interface. |