1. 堆概念
堆是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。
最大堆和最小堆是二叉堆的两种形式。
最大堆:根结点的键值是所有堆结点键值中最大者。
最小堆:根结点的键值是所有堆结点键值中最小者。
2. heap
树的最小元素在根部,为index 0.
heap包对任意实现了heap接口的类型提供堆操作。
heap是常用的实现优先队列的方法。要创建一个优先队列,实现一个具有使用(负的)优先级作为比较的依据的Less方法的Heap接口,如此一来可用Push添加项目而用Pop取出队列最高优先级的项目。
3. 类型接口
3.1 类型接口
heap包中核心是heap.Interface接口, 堆的基础存储是一个树形结构,可以用数组或是链表实现,通过heap的函数,可以建立堆并在堆上进行操作。
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包提供的各个函数进行操作,从而实现一个堆。
3.2 成员函数
heap包中提供了几个最基本的堆操作函数,包括Init,Fix,Push,Pop和Remove (其中up, down函数为非导出函数)。这些函数都通过调用前面实现接口里的方法,对堆进行操作。
// 一个堆在使用任何堆操作之前应先初始化。接受参数为实现了heap.Interface接口的对象。
func Init(h Interface)
// 在修改第i个元素后,调用本函数修复堆,比删除第i个元素后插入新元素更有效率。
func Fix(h Interface, i int)
// Push和Pop是一对标准堆操作,Push向堆添加一个新元素,Pop弹出并返回堆顶元素,而在push和pop操作不会破坏堆的结构
func Push(h Interface, x any)
func Pop(h Interface) any
// Remove删除堆中的第i个元素,并保持堆的约束性
func Remove(h Interface, i int) any
//使用案例
import (
"container/heap"
"fmt"
)
hp := &ItemHeap{}
heap.Init(hp)
heap.Push(hp, Item{key: i, value: i})
heap.Pop(hp)
3.3 小堆顶的实现
package main
import (
"container/heap"
"fmt"
)
// 小堆顶
type Item struct {
// 排序的关键词,key根据需求修改
key int
// value,万能的话可以用interface{}
value int
}
type ItemHeap []Item
func (h ItemHeap) Len() int {
return len(h)
}
func (h ItemHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h ItemHeap) Less(i, j int) bool {
// <是小顶堆,>是大顶堆
return h[i].key < h[j].key
}
// 实现heap.Interface接口定义的额外方法
func (h *ItemHeap) Push(item interface{}) {
*h = append(*h, item.(Item))
}
// 这个方法不是给用户使用的
func (h *ItemHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
hp := &ItemHeap{}
heap.Init(hp)
for i := 0; i < 10; i++ {
heap.Push(hp, Item{key: i, value: i})
}
for i := 100; i > 90; i-- {
heap.Push(hp, Item{key: i, value: i})
}
// 输出堆的长度,验证元素已插入
fmt.Printf("Heap length: %d\n", hp.Len())
//取出最小元素需要使用
fmt.Println(heap.Pop(hp))
}