README
¶
heap
Persistent pairing heap (priority queue) parameterized by a comparator. Based on Stone's Algorithms for Functional Programming (Ch 4).
All mutating operations return new heaps — the original is never modified. Heaps share structure internally, so copies are cheap.
What It Looks Like
// Min-heap of ints
h := heap.New(lof.IntAsc)
h = h.Insert(3).Insert(1).Insert(2)
// Peek at minimum
if v, ok := h.Min().Get(); ok {
fmt.Println(v) // 1
}
// Pop minimum and continue
v, rest, ok := h.Pop() // v=1, rest has {2, 3}
// Drain in sorted order
sorted := h.Collect() // [1 2 3]
// Merge two heaps
combined := h.Merge(h2)
Comparator Contract
The comparator determines priority: cmp(a, b) < 0 means a has higher priority than b. Use slice.Asc / slice.Desc or lof.IntAsc / lof.IntDesc to build comparators, or provide a custom func(T, T) int.
Merge requires the same comparator. Merge uses the receiver's comparator. If other was built with a different ordering, the merged heap's ordering is silently incorrect — no error or panic occurs.
Persistence
Every mutating operation returns a new heap. The old heap remains valid and unchanged:
h1 := heap.From(items, lof.IntAsc)
h2 := h1.Insert(x) // h1 still has original elements
h3 := h1.DeleteMin() // h1 still has original elements
Zero Value and Panics
The zero value of Heap[T] is an empty heap without a comparator. Queries are safe: IsEmpty, Len, Min, and Pop return sensible defaults. Mutating operations (Insert, DeleteMin, Merge) panic because no comparator is available. Always construct with New or From.
New and From panic if cmp is nil.
Operations
Create
New[T any](cmp func(T, T) int) Heap[T]— empty heap with comparatorFrom[T any](items []T, cmp func(T, T) int) Heap[T]— heap from slice (repeated Insert)
Core (return new heap)
.Insert(t)— add element.DeleteMin()— remove minimum (returns empty heap with comparator if already empty).Merge(other)— combine two heaps (both must use the same ordering)
Query
.Min()— peek at minimum (option.Option[T]), not-ok if empty.Pop()—(elem, rest, true)or(zero, empty, false)if empty.IsEmpty()— true if no elements.Len()— element count
Consume
.Collect()— all elements in sorted order (returns nil for empty heap)
Textbook pairing heap complexities: Insert and Merge are O(1), DeleteMin is O(log n) amortized. The persistent representation copies child-pointer slices during merge to preserve immutability, so constant factors are higher than an ephemeral implementation.
See pkg.go.dev for complete API documentation and the main README for installation.
Documentation
¶
Overview ¶
Package heap provides a persistent (immutable) priority queue backed by a pairing heap, parameterized by a comparator function.
Based on Stone's Algorithms for Functional Programming (Ch 4). The pairing merge strategy (Stone's heap-list-merger) gives O(1) insert and merge with O(log n) amortized delete-min.
Create heaps with New or From. The zero value is a valid empty heap for queries (IsEmpty, Min, Len) but panics on Insert, DeleteMin, and Merge because no comparator is available.
Use slice.Asc and slice.Desc from the slice package to build comparators:
h := heap.New(slice.Asc(Widget.Priority)) // min-heap by priority h := heap.New(slice.Desc(Widget.Priority)) // max-heap by priority
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap[T any] struct { // contains filtered or unexported fields }
Heap is a persistent priority queue. Operations return new heaps; the original is unchanged. The comparator determines ordering: negative means the first argument has higher priority.
func (Heap[T]) Collect ¶
func (h Heap[T]) Collect() []T
Collect returns all elements in sorted order. O(n log n). Returns nil for an empty heap. Stone's fold-heap applied with list + prepend.
func (Heap[T]) DeleteMin ¶
DeleteMin returns a new heap with the minimum element removed. Returns an empty heap (with comparator) if called on an empty heap. O(log n) amortized.
func (Heap[T]) Insert ¶
Insert returns a new heap with t added. O(1). Stone's heap-adjoiner: create a singleton bush, merge with root.
func (Heap[T]) Merge ¶
Merge returns a new heap combining h and other. O(1). Uses h's comparator. Both heaps must use the same ordering for correct results. Stone's merge-heaps.
Source Files