heap

Documentation

Index

• Constants
• type BucketHeap
  • func NewBucketHeap(buckets, capacity int) *BucketHeap
  • func (s *BucketHeap) Pop() interface{}
  • func (s *BucketHeap) Push(bucketIndex int, x interface{}) error

Constants

const (
	MAX_BUCKET_COUNT    = 100000 // 最大的桶数量限制，防止过量扩展桶
	MAX_FREE_NODE_COUNT = 16     // 最大缓存的pop个数，也是支持同时读的线程数
)

Types

type BucketHeap

type BucketHeap struct {
	// contains filtered or unexported fields
}

注意：不是线程安全的 一个高效的特殊小顶堆实现，结合桶排序的思路，针对节点的SortKey值域小且重复多的场景。 堆中的节点是一个 <bucketIndex int, x interface{}> 的二元组， bucketIndex用于决定 x 在 Heap 中的位置（SortKey）。

func NewBucketHeap

func NewBucketHeap(buckets, capacity int) *BucketHeap

buckets：桶的数量，桶是编号从0开始的连续自然数 capacity：在sorter中驻留的最大节点数量，若已满Push会报错

func (*BucketHeap) Pop

func (s *BucketHeap) Pop() interface{}

返回最小bucket中的一个元素，若没有返回nil 注意：Pop最多会产生MAX_FREE_NODE_COUNT个未被删除的Node，须及时Push，否则连续的MAX_FREE_NODE_COUNT+1次Pop会导致这个Node被泄漏

func (*BucketHeap) Push

func (s *BucketHeap) Push(bucketIndex int, x interface{}) error

向bucketIndex所在的桶插入一个元素x