Deprecated: moved into github.com/kitsunium/sdk/internal (ADR 0171), which no consumer imports; update with: go get github.com/kitsunium/sdk/pkg/v1/<family>@latest for each family you import && go mod tidy
README
¶
heap
Generic binary heap Heap[T] for the SDK kernel — stdlib-only, no domain
vocabulary. One type parameter and one comparison function; no Job, no
Priority, no interface to implement.
import (
"cmp"
"github.com/kitsunium/sdk/internal/kernel/heap"
)
h := heap.New(cmp.Compare[int]) // min-heap; reverse the arguments for a max-heap
h.Push(5)
h.Push(1)
top, ok := h.Pop() // 1, true
_, ok = h.Peek() // pure read: peeking does not mutate
It exists because container/heap is not generic: it is an algorithm over a
five-method interface, so every use site writes boilerplate, boxes each element
into any, and type-asserts it back out. BENCH.md measures the difference —
1.75× the time and one 16 B allocation per push.
Edges worth knowing:
New(nil)panics. There is no order the SDK can invent for an arbitraryT, so the missing comparison is refused at the call that omitted it rather than at the firstPush(ADR 0031, refusal branch).Pop/Peekreturn(T, bool)— an empty heap is a state, not a fault.- Ties pop in an unspecified order. A binary heap is not stable; add a
sequence number to
Tif you need FIFO among equals. - Not safe for concurrent use. The caller picks the lock.
See CLAUDE.md for the design and BENCH.md for the numbers.
Documentation
¶
Overview ¶
Package heap provides Heap[T], a binary heap ordered by a comparison function the caller supplies. It is a kernel primitive: stdlib-only, and domain-neutral down to the signatures — one type parameter and one comparison, with no Job, no Task and no Priority anywhere in the API.
Why not container/heap ¶
container/heap exists and cannot be used cleanly here. It is an ALGORITHM over an interface the caller must implement: five methods (Len, Less, Swap, Push, Pop) on a named slice type, where Push takes `any` and Pop returns `any`. Every use site therefore writes the same boilerplate, boxes each element on the way in, and type-asserts it on the way out — a conversion the compiler cannot check and the reader has to trust. That was the right design in 2011; it predates type parameters.
The generic version costs one comparison function at construction and nothing at all at the call site.
Order ¶
cmp follows the cmp.Compare / slices.SortFunc convention: negative when a sorts before b, zero when they tie, positive otherwise. The element that sorts FIRST is the one at the top, so cmp.Compare[int] gives a MIN-heap and a max-heap is the same function with its arguments reversed. Ties pop in an unspecified order — a binary heap is not stable, and no amount of care in the comparison makes it so.
Concurrency ¶
A Heap is NOT safe for concurrent use. That is deliberate: a lock inside would be paid by every caller, including the many that hold a heap inside a structure they already serialise. The caller picks the lock, or does not need one.
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 binary heap ordered by the comparison given to New.
The zero value is NOT usable — a heap with no comparison has no order — so construct with New. Not safe for concurrent use.
func New ¶
New builds an empty Heap ordered by cmp.
A nil cmp PANICS, at the call that made the mistake. There is no order the SDK can invent for an arbitrary T, so ADR 0031's other branch — clamp to a working default — has nothing to clamp to; this is the refusal branch. It is delivered as a panic rather than an error because the kernel has no error budget for programmer faults (recycler and clock take the same position) and because the alternative, a Heap that panics on the first Push, moves the crash away from the line that caused it.
func (*Heap[T]) Peek ¶
Peek returns the top element without removing it, and reports whether there was one. It does not mutate the heap, so unlike a cache read it really is a getter.
func (*Heap[T]) Pop ¶
Pop removes and returns the top element, in O(log n), and reports whether there was one.
It returns (zero, false) on an empty heap rather than panicking: emptiness is an ordinary state of a queue, not a programmer error, and the (T, bool) shape is the same one kernel/cache uses for a miss.
Source Files