堆(heap)是一棵完全二叉树,堆满足下列性质:堆中某个节点的值总是不大于或不小于其父节点的值。
介绍
- 大根堆:堆中任意节点的值都大于等于其子节点,反之为小根堆
- 堆可以使用数组表示,且下标为
i的节点的父节点的小标为(i-1)/2,其左右节点分别为(2i+1)和(2i+2)
使用场景
- 使用堆实现超时缓存,如 ssl 证书的到期时间
- 按 key 的到期时间把 key 插入小根堆中
- 周期扫描堆顶的元素,如果它的到期时间早于当前时刻(过期),则将其从堆顶删除
堆的实现
golang 中 container/heap 实现了小根堆,使用时需要实现 heap.Interface 接口(继承自 sort.Interface),共包含 5 个方法:
Len() intLess(i, j int) boolSwap(i, j int)Push(x any)Pop() any
IntHeap 示例:
// This example demonstrates an integer heap built using the heap interface.
package main
import (
"container/heap"
"fmt"
)
// An IntHeap is a min-heap of ints.
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 any) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
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- Cache 超时淘汰实现(结合 Map 与小根堆)
type CacheItem struct {
key string
value any
deadline int64 // 到期时间戳
}
// 假设 cacheMap 存储键值数据,h 为按 deadline 排序的小根堆
var (
cacheMap = make(map[string]*CacheItem)
h = &ItemHeap{}
)
func cleanCache() {
for {
if h.Len() == 0 {
time.Sleep(100 * time.Millisecond)
continue
}
now := time.Now().Unix()
top := (*h)[0]
if top.deadline <= now {
// 从堆顶弹出最早到期的元素
expired := heap.Pop(h).(*CacheItem)
// 同步从缓存 map 中删除
delete(cacheMap, expired.key)
} else {
time.Sleep(100 * time.Millisecond)
}
}
}最近更新
最新评论