Skip to content

Instantly share code, notes, and snippets.

@jba

jba/gist:8b83d62a6cb6b3f6ab9779f50584aa64

Created December 6, 2025 17:11
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jba/8b83d62a6cb6b3f6ab9779f50584aa64 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jba/8b83d62a6cb6b3f6ab9779f50584aa64 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
package heap // import "github.com/jba/heap"
Package heap provides min-heap data structures.
TYPES
type Heap[T cmp.Ordered] struct {
// Has unexported fields.
}
Heap is a min-heap for ordered types.
func New[T cmp.Ordered]() *Heap[T]
New creates a new min-heap for ordered types.
func (h *Heap[T]) All() iter.Seq[T]
All returns an iterator over all elements in the heap. The first element
yielded is guaranteed to be the minimum. The order of other elements is
unspecified.
If the heap hasn't been built yet, All builds it before iterating.
func (h *Heap[T]) Build()
Build rebuilds the heap in O(n) time. Call this after inserting multiple
elements to avoid the cost of building the heap on the first call to Min or
ExtractMin.
func (h *Heap[T]) Clear()
Clear removes all elements from the heap.
func (h *Heap[T]) ExtractMin() T
ExtractMin removes and returns the minimum element from the heap. Panics if
the heap is empty.
The first call to ExtractMin builds the heap if it hasn't been built yet.
func (h *Heap[T]) Insert(value T)
Insert adds an element to the heap.
Before the first call to other methods such as Min or ExtractMin, Insert
simply appends to an internal slice without maintaining the heap invariant.
Call Build explicitly if you want to ensure the heap is built after a batch
of insertions.
func (h *Heap[T]) InsertItem(value T) Item
InsertItem adds an element to the heap and returns an Item that can be used
to delete or adjust the element later.
Before the first call to other methods such as Min or ExtractMin, InsertItem
simply appends to an internal slice without maintaining the heap invariant.
Call Build explicitly if you want to ensure the heap is built after a batch
of insertions.
func (h *Heap[T]) Len() int
Len returns the number of elements in the heap.
func (h *Heap[T]) Min() T
Min returns the minimum element in the heap without removing it. Panics if
the heap is empty.
The first call to Min builds the heap if it hasn't been built yet.
type HeapFunc[T any] struct {
// Has unexported fields.
}
HeapFunc is a min-heap for any type with a custom comparison function.
func NewFunc[T any](compare func(T, T) int) *HeapFunc[T]
NewFunc creates a new min-heap with a custom comparison function. The
comparison function should return a negative value if a < b, zero if a == b,
and a positive value if a > b.
func (h *HeapFunc[T]) All() iter.Seq[T]
All returns an iterator over all elements in the heap. The first element
yielded is guaranteed to be the minimum. The order of other elements is
unspecified.
If the heap hasn't been built yet, All builds it before iterating.
func (h *HeapFunc[T]) Build()
Build rebuilds the heap in O(n) time. Call this after inserting multiple
elements to avoid the cost of building the heap on the first call to Min or
ExtractMin.
func (h *HeapFunc[T]) Clear()
Clear removes all elements from the heap.
func (h *HeapFunc[T]) ExtractMin() T
ExtractMin removes and returns the minimum element from the heap. Panics if
the heap is empty.
The first call to ExtractMin builds the heap if it hasn't been built yet.
func (h *HeapFunc[T]) Insert(value T)
Insert adds an element to the heap.
Before the first call to other methods such as Min or ExtractMin, Insert
simply appends to an internal slice without maintaining the heap invariant.
Call Build explicitly if you want to ensure the heap is built after a batch
of insertions.
func (h *HeapFunc[T]) InsertItem(value T) Item
InsertItem adds an element to the heap and returns an Item that can be used
to delete or adjust the element later.
Before the first call to other methods such as Min or ExtractMin, InsertItem
simply appends to an internal slice without maintaining the heap invariant.
Call Build explicitly if you want to ensure the heap is built after a batch
of insertions.
func (h *HeapFunc[T]) Len() int
Len returns the number of elements in the heap.
func (h *HeapFunc[T]) Min() T
Min returns the minimum element in the heap without removing it. Panics if
the heap is empty.
The first call to Min builds the heap if it hasn't been built yet.
type Item struct {
// Has unexported fields.
}
Item represents an element in the heap and can be used to delete or modify
it.
func (item Item) Adjust()
Adjust restores the heap invariant after the item's value has been changed.
Call this method after modifying the value of the element that this Item
represents. If the item has been deleted or the heap has been cleared,
Adjust does nothing.
func (item Item) Delete()
Delete removes this item from the heap. If the item has already been deleted
or the heap has been cleared, Delete does nothing.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment