“Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming. 数据为王。如果你选择了合适的数据结构并进行了良好的组织,算法通常会变得显而易见。_编程的核心在于数据结构,而非算法_。
3.用途:HeapMap 适合需要频繁按键排序和快速查找的场景,比如带有优先级的缓存、调度系统、任务优先队列等。
2.哈希映射(Map):用来存储每个键值对,并支持通过键快速查找元素。
type Entry[K comparable, V, P any] struct { Key K Value V Priority P index int } type heapmap[K comparable, V, P any] struct { h pq[K, V, P] m map[K]*Entry[K, V, P] }Entry 代表这个数据结构中的一个节点 (元素、条目) , 它包含 key、value 值,还有优先级,index 记录它在堆的实现数组中的索引。heapmap 代表 HeapMap 的实现,它包含两个字段,第一个字段其实就是 Heap 的实现,为了方便实现泛型,它就自己实现了一个堆。第二个字段就是一个 map 对象了。
func (hm *heapmap[K, V, P]) Len() int { return len(hm.m) }读取h字段或者m字段的长度都可以。
func (hm *heapmap[K, V, P]) Peek() (Entry[K, V, P], bool) { if hm.Empty() { return Entry[K, V, P]{}, false } return *hm.h.entries[0], true }Pop 方法
func (hm *heapmap[K, V, P]) Pop() (Entry[K, V, P], bool) { if hm.Empty() { return Entry[K, V, P]{}, false } e := *heap.Pop(&hm.h).(*Entry[K, V, P]) delete(hm.m, e.Key) return e, true }注意涉及到元素的删除操作,要同时删除 map 中的元素。
// 堆代码 duidaima.com func (hm *heapmap[K, V, P]) Set(key K, value V, priority P) { if e, ok := hm.m[key]; ok { e.Value = value e.Priority = priority heap.Fix(&hm.h, e.index) return } e := &Entry[K, V, P]{ Key: key, Value: value, Priority: priority, } heap.Push(&hm.h, e) hm.m[key] = e }Set 方法有两个功能。如果元素的 Key 已经存在,那么就是更新元素,并且根据优先级进行调整。 如果元素的 Key 不存在,那么就是插入元素。
func (hm *heapmap[K, V, P]) Get(key K) (Entry[K, V, P], bool) { if e, ok := hm.m[key]; ok { return *e, true } return Entry[K, V, P]{}, false }有一点你需要注意的是,这个数据结构不是线程安全的,如果你需要线程安全的话,你可以使用 sync.Mutex/sync.RWMutex 来保护它。