Golang 大小堆的实现

[dduo518]

Golang 大小堆的实现

堆 这种数据结构是比较难搞的一种，但是它在实际工程中的实用性又比较高，能够有效的解决实际中遇见的问题。
堆的插入更新调整的时间复杂度通常在O(lgN),但是查找最大或者最小的元素是O(1)的时间复杂度。

二叉树

堆实际上也是一个不完全的二叉树，是二叉树的一个变种，通常二叉树的左右子节点都具有大小特性，

二叉树实际上底层数据结构是一个数组，且具有以下几种特性

1. 儿子兄弟表示
2. 每个节点只有俩个节点 左节点为儿子节点，右节点为兄弟节点
   由根节点 和称为左子树和右子树 的俩个不相交的二叉树组成
   重要性质
1. 一个二叉树第i层 的最大节点数为 2^(i-1) ;i>1
2. 深度为K的二叉树有最大的节点数 为 2^k-1 个节点
   2^(1-1)+2^(2-1)+2^(3-1)...+2^(k-1) = 2^k-1 (完美二叉树)
3. 任何非空二叉树 叶子节点(n0)的个数 等于 度为2(2个儿子节点 n2)的非叶子节点的个数+1 n0 = n2+1
   4.对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。
   而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2*n2。所以，n 用另外一种方式表示为 n=n1+2*n2+1。

堆（heap）

那么在 go语言中是如何要实现一个heap的呢，其实在官方标准库 container/heap 已经给你实现了，你只需要根据自己实际情况进行接口实现即可。

在go的标准库 container/heap 以后给出了现存的堆结构我们只需要进行接口实现和调用接口即可。

在普通的堆实现中，我们只需要实现几个接口

type Interface interface {
    Less(i, j int) bool // 这个实现决定了是大顶堆还是小顶堆
    Swap(i, j int)
    Len() int
	Push(x any)
	Pop() any  
}

examples

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{}) {
	*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() {
    var h = &IntHeap{}
    heap.Init(h) // 初始化
    heap.Push(h, 1) // 插入一个元素
    heap.Push(h, 2)
    heap.Push(h, 3)
    heap.Push(h, 4)
    heap.Push(h, 5)
    heap.Push(h, 6)
    heap.Push(h, 7)
    log.Println(heap.Pop(h)) // 弹出堆顶
    heap.Push(h, 7)
}

堆的使用场景

优先队列

在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队

高性能定时器

有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间（比如 1 秒），就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。
按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。

它先拿队首任务的执行时间点，与当前时间点相减，得到一个时间间隔 T。

这个时间间隔 T 就是，从当前时间开始，需要等待多久，才会有第一个任务需要被执行。

这样，定时器就可以设定在 T 秒之后，再来执行任务。从当前时间点到（T-1）秒这段时间里，定时器都不需要做任何事情。

当 T 秒时间过去之后，定时器取优先级队列中队首的任务执行。然后再计算新的队首任务的执行时间点与当前时间点的差值，把这个值作为定时器执行下一个任务需要等待的时间。