1// Package heap is a binary min-heap / priority queue over string items with2// integer priorities, as a pure, reusable package.3//4// Go's container/heap makes the caller implement five methods and hands back an5// interface; that indirection buys generality this chain does not need and6// costs gas it does. This is the concrete data structure instead: an implicit7// 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 insertion10// sequence, so two heaps fed the same items in the same order always pop the11// same sequence — a heap that reordered ties by allocation address would make a12// Render vary between nodes, which is a consensus bug rather than a cosmetic13// one.14//15// A live demo of this package is at16// [r/moul/x/daily/heapdemo](/r/moul/x/daily/heapdemo/v0).17package heap1819// MaxItems bounds the heap so gas stays predictable.20const MaxItems = 40962122type item struct {23 value string24 priority int25 seq int // insertion sequence, breaks priority ties26}2728// Heap is a binary min-heap: the lowest priority pops first.29type Heap struct {30 items []item31 next int // monotonic insertion counter32 max bool33}3435// New returns an empty min-heap (lowest priority pops first).36func New() *Heap { return &Heap{} }3738// NewMax returns an empty max-heap (highest priority pops first). Ties are39// still broken by insertion order, oldest first.40func NewMax() *Heap { return &Heap{max: true} }4142// Len returns the number of items.43func (h *Heap) Len() int { return len(h.items) }4445// IsEmpty reports whether the heap holds nothing.46func (h *Heap) IsEmpty() bool { return len(h.items) == 0 }4748// IsMax reports whether this is a max-heap.49func (h *Heap) IsMax() bool { return h.max }5051// 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.priority56 }57 return a.priority < b.priority58 }59 // Total order: equal priorities pop oldest-first, in BOTH heap kinds.60 return a.seq < b.seq61}6263// 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 false67 }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 true72}7374// 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, false78 }79 return h.items[0].value, h.items[0].priority, true80}8182// 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, false86 }87 top := h.items[0]88 last := len(h.items) - 189 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, true95}9697// 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 out104 }105 out = append(out, v)106 }107}108109// 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 cp114}115116func (h *Heap) up(i int) {117 for i > 0 {118 parent := (i - 1) / 2119 if !h.less(h.items[i], h.items[parent]) {120 return121 }122 h.items[i], h.items[parent] = h.items[parent], h.items[i]123 i = parent124 }125}126127func (h *Heap) down(i int) {128 n := len(h.items)129 for {130 left := 2*i + 1131 if left >= n {132 return133 }134 best := left135 if right := left + 1; right < n && h.less(h.items[right], h.items[left]) {136 best = right137 }138 if !h.less(h.items[best], h.items[i]) {139 return140 }141 h.items[i], h.items[best] = h.items[best], h.items[i]142 i = best143 }144}145Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.