堆

发布时间: 更新时间: 总字数:566 阅读时间:2m 作者:IP:上海 网址

堆(heap)是一棵完全二叉树,堆满足下列性质:堆中某个节点的值总是不大于或不小于其父节点的值。

介绍

  • 大根堆:堆中任意节点的值都大于等于其子节点,反之为小根堆
  • 堆可以使用数组表示,且下标为 i 的节点的父节点的小标为 (i-1)/2,其左右节点分别为 (2i+1) 和 (2i+2)

使用场景

  • 使用堆实现超时缓存,如 ssl 证书的到期时间
    • 按 key 的到期时间把 key 插入小根堆中
    • 周期扫描堆顶的元素,如果它的到期时间早于当前时刻(过期),则将其从堆顶删除

堆的实现

golang 中 container/heap 实现了小根堆,使用时需要实现 heap.Interface 接口(继承自 sort.Interface),共包含 5 个方法:

  • Len() int
  • Less(i, j int) bool
  • Swap(i, j int)
  • Push(x any)
  • Pop() any

IntHeap 示例:

go
// 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))
	}
}

输出:

text
minimum: 1
1 2 3 5
  • Cache 超时淘汰实现(结合 Map 与小根堆)
go
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)
		}
	}
}