heap.gno

  1// Package heap is a binary min-heap / priority queue over string items with
  2// integer priorities, as a pure, reusable package.
  3//
  4// Go's container/heap makes the caller implement five methods and hands back an
  5// interface; that indirection buys generality this chain does not need and
  6// costs gas it does. This is the concrete data structure instead: an implicit
  7// binary heap in a slice, Push/Pop in O(log n), Peek in O(1).
  8//
  9// Ordering is TOTAL and deterministic. Equal priorities are broken by insertion
 10// sequence, so two heaps fed the same items in the same order always pop the
 11// same sequence — a heap that reordered ties by allocation address would make a
 12// Render vary between nodes, which is a consensus bug rather than a cosmetic
 13// one.
 14//
 15// A live demo of this package is at
 16// [r/moul/x/daily/heapdemo](/r/moul/x/daily/heapdemo/v0).
 17package heap
 18
 19// MaxItems bounds the heap so gas stays predictable.
 20const MaxItems = 4096
 21
 22type item struct {
 23	value    string
 24	priority int
 25	seq      int // insertion sequence, breaks priority ties
 26}
 27
 28// Heap is a binary min-heap: the lowest priority pops first.
 29type Heap struct {
 30	items []item
 31	next  int // monotonic insertion counter
 32	max   bool
 33}
 34
 35// New returns an empty min-heap (lowest priority pops first).
 36func New() *Heap { return &Heap{} }
 37
 38// NewMax returns an empty max-heap (highest priority pops first). Ties are
 39// still broken by insertion order, oldest first.
 40func NewMax() *Heap { return &Heap{max: true} }
 41
 42// Len returns the number of items.
 43func (h *Heap) Len() int { return len(h.items) }
 44
 45// IsEmpty reports whether the heap holds nothing.
 46func (h *Heap) IsEmpty() bool { return len(h.items) == 0 }
 47
 48// IsMax reports whether this is a max-heap.
 49func (h *Heap) IsMax() bool { return h.max }
 50
 51// less reports whether a should pop before b.
 52func (h *Heap) less(a, b item) bool {
 53	if a.priority != b.priority {
 54		if h.max {
 55			return a.priority > b.priority
 56		}
 57		return a.priority < b.priority
 58	}
 59	// Total order: equal priorities pop oldest-first, in BOTH heap kinds.
 60	return a.seq < b.seq
 61}
 62
 63// Push adds value with the given priority. Returns false when the heap is full.
 64func (h *Heap) Push(value string, priority int) bool {
 65	if len(h.items) >= MaxItems {
 66		return false
 67	}
 68	h.items = append(h.items, item{value: value, priority: priority, seq: h.next})
 69	h.next++
 70	h.up(len(h.items) - 1)
 71	return true
 72}
 73
 74// Peek returns the item that would pop next, without removing it.
 75func (h *Heap) Peek() (value string, priority int, ok bool) {
 76	if len(h.items) == 0 {
 77		return "", 0, false
 78	}
 79	return h.items[0].value, h.items[0].priority, true
 80}
 81
 82// Pop removes and returns the next item.
 83func (h *Heap) Pop() (value string, priority int, ok bool) {
 84	if len(h.items) == 0 {
 85		return "", 0, false
 86	}
 87	top := h.items[0]
 88	last := len(h.items) - 1
 89	h.items[0] = h.items[last]
 90	h.items = h.items[:last]
 91	if len(h.items) > 0 {
 92		h.down(0)
 93	}
 94	return top.value, top.priority, true
 95}
 96
 97// Drain pops everything, returning values in pop order. The heap ends empty.
 98func (h *Heap) Drain() []string {
 99	out := make([]string, 0, len(h.items))
100	for {
101		v, _, ok := h.Pop()
102		if !ok {
103			return out
104		}
105		out = append(out, v)
106	}
107}
108
109// Clone returns an independent copy.
110func (h *Heap) Clone() *Heap {
111	cp := &Heap{items: make([]item, len(h.items)), next: h.next, max: h.max}
112	copy(cp.items, h.items)
113	return cp
114}
115
116func (h *Heap) up(i int) {
117	for i > 0 {
118		parent := (i - 1) / 2
119		if !h.less(h.items[i], h.items[parent]) {
120			return
121		}
122		h.items[i], h.items[parent] = h.items[parent], h.items[i]
123		i = parent
124	}
125}
126
127func (h *Heap) down(i int) {
128	n := len(h.items)
129	for {
130		left := 2*i + 1
131		if left >= n {
132			return
133		}
134		best := left
135		if right := left + 1; right < n && h.less(h.items[right], h.items[left]) {
136			best = right
137		}
138		if !h.less(h.items[best], h.items[i]) {
139			return
140		}
141		h.items[i], h.items[best] = h.items[best], h.items[i]
142		i = best
143	}
144}