Capstone: ship a Go DSA package

godsa/
├── go.mod                module github.com/you/godsa
├── README.md             what it is, install, examples, benchmark table
├── LICENSE               MIT or Apache-2.0
├── .github/workflows/ci.yml
├── stack/   stack.go  stack_test.go  example_test.go
├── queue/   …
├── heap/    …
├── dsu/     …
└── trie/    …

// Package heap provides a generic binary heap.
package heap
 
// Heap is a binary heap ordered by a less function.
// The zero value is not usable; create one with New.
type Heap[T any] struct {
	data []T
	less func(a, b T) bool
}
 
// New returns an empty heap. If less(a, b) reports a < b, Pop returns the smallest element.
func New[T any](less func(a, b T) bool) *Heap[T] {
	return &Heap[T]{less: less}
}
 
// Len returns the number of elements.
func (h *Heap[T]) Len() int { return len(h.data) }
 
// Push adds v in O(log n).
func (h *Heap[T]) Push(v T) { /* sift up, as in the heaps lesson */ }
 
// Pop removes and returns the top element in O(log n).
// ok is false when the heap is empty.
func (h *Heap[T]) Pop() (v T, ok bool) { /* sift down */ }

// example_test.go
package heap_test
 
import (
	"fmt"
 
	"github.com/you/godsa/heap"
)
 
func ExampleHeap() {
	h := heap.New(func(a, b int) bool { return a < b })
	for _, v := range []int{5, 1, 3} {
		h.Push(v)
	}
	v, _ := h.Pop()
	fmt.Println(v)
	// Output: 1
}

package main
 
import (
	"fmt"
	"iter"
)
 
// Heap is a binary heap ordered by a less function.
type Heap[T any] struct {
	data []T
	less func(a, b T) bool
}
 
// New returns an empty heap. If less(a, b) reports a < b, Pop returns the smallest element.
func New[T any](less func(a, b T) bool) *Heap[T] { return &Heap[T]{less: less} }
 
// Len returns the number of elements.
func (h *Heap[T]) Len() int { return len(h.data) }
 
// Push adds v in O(log n).
func (h *Heap[T]) Push(v T) {
	h.data = append(h.data, v)
	for i := len(h.data) - 1; i > 0; {
		p := (i - 1) / 2
		if !h.less(h.data[i], h.data[p]) {
			break
		}
		h.data[i], h.data[p] = h.data[p], h.data[i]
		i = p
	}
}
 
// Pop removes and returns the top element in O(log n). ok is false when the heap is empty.
func (h *Heap[T]) Pop() (v T, ok bool) {
	if len(h.data) == 0 {
		return v, false
	}
	v = h.data[0]
	last := len(h.data) - 1
	h.data[0] = h.data[last]
	h.data = h.data[:last]
	for i := 0; ; {
		small := i
		for _, c := range []int{2*i + 1, 2*i + 2} {
			if c < len(h.data) && h.less(h.data[c], h.data[small]) {
				small = c
			}
		}
		if small == i {
			break
		}
		h.data[i], h.data[small] = h.data[small], h.data[i]
		i = small
	}
	return v, true
}
 
// All yields the elements in internal (heap) order, without removing them.
func (h *Heap[T]) All() iter.Seq[T] {
	return func(yield func(T) bool) {
		for _, v := range h.data {
			if !yield(v) {
				return
			}
		}
	}
}
 
type job struct {
	name string
	prio int
}
 
func main() {
	nums := New(func(a, b int) bool { return a < b })
	for _, v := range []int{5, 1, 4, 2, 3} {
		nums.Push(v)
	}
	fmt.Print("heap order:")
	for v := range nums.All() {
		fmt.Print(" ", v)
	}
	fmt.Print("\npop order: ")
	for nums.Len() > 0 {
		v, _ := nums.Pop()
		fmt.Print(" ", v)
	}
	_, ok := nums.Pop()
	fmt.Println("\npop on empty, ok =", ok)
 
	// The same type works for any element, ordered by any rule.
	jobs := New(func(a, b job) bool { return a.prio > b.prio })
	jobs.Push(job{"email", 1})
	jobs.Push(job{"outage", 9})
	jobs.Push(job{"tests", 5})
	top, _ := jobs.Pop()
	fmt.Println("most urgent:", top.name)
}

heap order: 1 2 4 5 3
pop order:  1 2 3 4 5
pop on empty, ok = false
most urgent: outage

package main
 
import (
	"fmt"
	"math/rand"
	"slices"
)
 
type Heap[T any] struct {
	data []T
	less func(a, b T) bool
}
 
func New[T any](less func(a, b T) bool) *Heap[T] { return &Heap[T]{less: less} }
 
func (h *Heap[T]) Len() int { return len(h.data) }
 
func (h *Heap[T]) Push(v T) {
	h.data = append(h.data, v)
	for i := len(h.data) - 1; i > 0; {
		p := (i - 1) / 2
		if !h.less(h.data[i], h.data[p]) {
			break
		}
		h.data[i], h.data[p] = h.data[p], h.data[i]
		i = p
	}
}
 
func (h *Heap[T]) Pop() (T, bool) {
	var zero T
	if len(h.data) == 0 {
		return zero, false
	}
	top := h.data[0]
	last := len(h.data) - 1
	h.data[0] = h.data[last]
	h.data = h.data[:last]
	for i := 0; ; {
		l, r, m := 2*i+1, 2*i+2, i
		if l < len(h.data) && h.less(h.data[l], h.data[m]) {
			m = l
		}
		if r < len(h.data) && h.less(h.data[r], h.data[m]) {
			m = r
		}
		if m == i {
			break
		}
		h.data[i], h.data[m] = h.data[m], h.data[i]
		i = m
	}
	return top, true
}
 
// Property: pushing any values and popping them all yields sorted order.
func main() {
	failures := 0
	for trial := range 1000 {
		n := rand.Intn(50)
		in := make([]int, n)
		for i := range in {
			in[i] = rand.Intn(100) - 50
		}
		h := New(func(a, b int) bool { return a < b })
		for _, v := range in {
			h.Push(v)
		}
		var out []int
		for h.Len() > 0 {
			v, _ := h.Pop()
			out = append(out, v)
		}
		if !slices.IsSorted(out) || len(out) != n {
			failures++
			fmt.Println("trial", trial, "failed on", in)
		}
	}
	_, ok := New(func(a, b int) bool { return a < b }).Pop()
	fmt.Println("failures:", failures, "| pop on empty ok:", ok)
}

failures: 0 | pop on empty ok: false

# .github/workflows/ci.yml
name: ci
on: [push, pull_request]
jobs:
  test:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4
      - uses: actions/setup-go@v5
        with:
          go-version: "1.25"
      - run: go vet ./...
      - run: go test -race ./...

git tag v0.1.0
git push origin v0.1.0