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)
When to Use heap
// TopK returns the k largest items without sorting the full slice.
// Uses a min-heap of size k: insert each item, evict the smallest
// when the heap exceeds k. O(n log k) vs O(n log n) for full sort.
func TopK(items []int, k int) []int {
h := heap.New(lof.IntAsc)
for _, v := range items {
h = h.Insert(v)
if h.Len() > k {
h = h.DeleteMin()
}
}
return h.Collect()
}
Other common uses: merging K sorted sources (log files, database shards) and priority scheduling. For ephemeral priority queues where mutation is fine, use container/heap. This package is for when you need persistence — undo, branching, or concurrent readers with no locking.
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 ¶
Examples ¶
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 From ¶
From builds a heap from a slice, ordered by cmp. Panics if cmp is nil.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/binaryphile/fluentfp/heap"
)
func main() {
// Build a heap from a slice.
h := heap.From([]int{5, 3, 1, 4, 2}, cmp.Compare)
fmt.Println(h.Collect())
}
Output: [1 2 3 4 5]
func New ¶
New returns an empty heap ordered by cmp. Panics if cmp is nil.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/binaryphile/fluentfp/heap"
)
func main() {
// Priority queue: smallest number has highest priority.
h := heap.New[int](cmp.Compare)
h = h.Insert(3).Insert(1).Insert(2)
fmt.Println(h.Min().Or(0))
}
Output: 1
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.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/binaryphile/fluentfp/heap"
)
func main() {
// Collect drains the heap in sorted order.
h := heap.From([]string{"banana", "apple", "cherry"}, cmp.Compare)
fmt.Println(h.Collect())
}
Output: [apple banana cherry]
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.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/binaryphile/fluentfp/heap"
)
func main() {
// Merge two heaps in O(1).
a := heap.From([]int{1, 3, 5}, cmp.Compare)
b := heap.From([]int{2, 4, 6}, cmp.Compare)
merged := a.Merge(b)
fmt.Println(merged.Collect())
}
Output: [1 2 3 4 5 6]
func (Heap[T]) Pop ¶
Pop returns the minimum element, the remaining heap, and true. Returns zero T, the receiver (preserving comparator), and false if empty. Stone's heap-extractor.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/binaryphile/fluentfp/heap"
)
func main() {
// Pop returns the minimum, the remaining heap, and true.
h := heap.From([]int{3, 1, 2}, cmp.Compare)
min, rest, ok := h.Pop()
fmt.Printf("min=%d ok=%t remaining=%d\n", min, ok, rest.Len())
}
Output: min=1 ok=true remaining=2
Source Files