container/heap, list, and ring

container/heap, list, and ring

Overview

The container packages implement classic structures not in the language: heap (priority queue), doubly linked list, and ring.

container/heap

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)        { *h = append(*h, x.(int)) }
func (h *intHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

h := &intHeap{3, 1, 2}
heap.Init(h)
heap.Push(h, 0)
x := heap.Pop(h).(int) // 0

Use for schedulers, merge-k-sorted, Dijkstra.

container/list

l := list.New()
e := l.PushBack("b")
l.PushFront("a")
l.InsertAfter("c", e)
for e := l.Front(); e != nil; e = e.Next() {
    fmt.Println(e.Value)
}

Prefer slices unless you need O(1) remove from middle with handles.

container/ring

r := ring.New(3)
for i := 0; i < r.Len(); i++ {
    r.Value = i
    r = r.Next()
}
r.Do(func(v any) { fmt.Println(v) })

Round-robin buffers.

Rules

Prefer	When
slices + sort	Simple ordered data
heap	Repeated min/max extract
list	Heavy middle splice with element pointers

Try next

1. Top-K largest with min-heap of size K.
   
2. LRU sketch: map + list.
   
3. Ring for N worker round-robin.