堆

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

介绍

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

使用场景

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

堆的实现

golang 中 container/heap 实现了小根堆，使用时需要定义一个 struct，并实现以下接口：

• func (h IntHeap) Len() int
• func (h IntHeap) Less(i, j int) bool
• func (h IntHeap) Swap(i, j int)

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 的实现

func cleanCache() {
  for {
    if h.Len() == 0 {
      time.Sleep(100 * time.Millisecond)
      continue
    }

    now := int(time.Now().Unix())
    top := h[0]
    if top.deadline < now {
      heap.Pop(&h)
      delete(h, top.value)
    } else {
      time.Sleep(100 * time.Millisecond)
    }
  }
}