heapx

Documentation

Index

• type GreaterThanable
• type Heap
  • func NewMax[T constraints.Ordered](data ...T) *Heap[T]
  • func NewMaxI[T GreaterThanable[T]](data ...T) *Heap[T]
  • func NewMin[T constraints.Ordered](data ...T) *Heap[T]
  • func NewMinI[T LesserThanable[T]](data ...T) *Heap[T]
  • func NewWith[T any](less func(T, T) bool, data ...T) *Heap[T]
  • func (h *Heap[T]) Data() []T
  • func (h *Heap[T]) Fix(i int)
  • func (h *Heap[T]) IsEmpty() bool
  • func (h *Heap[T]) Len() int
  • func (h *Heap[T]) Pop() T
  • func (h *Heap[T]) Push(x T)
  • func (h *Heap[T]) Remove(i int) T
  • func (h *Heap[T]) Snapshot() []T
• type LesserThanable

Types

type GreaterThanable

type GreaterThanable[T any] interface {
	// GreaterThan returns true if the current value is greater than the given value.
	GreaterThan(T) bool
}

GreaterThanable represents types that can be compared with "greater than" operation. Types implementing this interface can be used in max heaps.

type Heap

type Heap[T any] struct {
	// contains filtered or unexported fields
}

Heap is a generic heap implementation based on container/heap. It supports both min and max heaps, and can work with custom comparison functions. The heap maintains the property that the top element is always the "least" according to the comparison function.

func NewMax

func NewMax[T constraints.Ordered](data ...T) *Heap[T]

NewMax creates a new max heap for ordered types. Example:

h := NewMax(1, 3, 5, 2, 4)
h.Pop() // returns 5
h.Pop() // returns 4

func NewMaxI

func NewMaxI[T GreaterThanable[T]](data ...T) *Heap[T]

NewMaxI creates a new max heap for types implementing GreaterThanable. Example:

type MyInt int
func (a MyInt) GreaterThan(b MyInt) bool { return a > b }
h := NewMaxI(MyInt(1), MyInt(3), MyInt(5))
h.Pop() // returns MyInt(5)

func NewMin

func NewMin[T constraints.Ordered](data ...T) *Heap[T]

NewMin creates a new min heap for ordered types. Example:

h := NewMin(5, 3, 1, 4, 2)
h.Pop() // returns 1
h.Pop() // returns 2

func NewMinI

func NewMinI[T LesserThanable[T]](data ...T) *Heap[T]

NewMinI creates a new min heap for types implementing LesserThanable. Example:

type MyInt int
func (a MyInt) LesserThan(b MyInt) bool { return a < b }
h := NewMinI(MyInt(5), MyInt(3), MyInt(1))
h.Pop() // returns MyInt(1)

func NewWith

func NewWith[T any](less func(T, T) bool, data ...T) *Heap[T]

NewWith creates a new heap with a custom comparison function. The less function should return true if a is considered less than b. The heap will maintain the property that the top element is the "least" according to this function. Example:

// Create a min heap based on absolute values
h := NewWith(func(a, b int) bool {
    return abs(a) < abs(b)
}, -5, 2, -3, 4, -1)
h.Pop() // returns -1 (smallest absolute value)

func (*Heap[T]) Data

func (h *Heap[T]) Data() []T

func (*Heap[T]) Fix

func (h *Heap[T]) Fix(i int)

Fix re-establishes the heap ordering after the element at index i has been changed. This is useful when the element's value has been modified in a way that could violate the heap property. Panics if i is out of range.

func (*Heap[T]) IsEmpty

func (h *Heap[T]) IsEmpty() bool

func (*Heap[T]) Len

func (h *Heap[T]) Len() int

func (*Heap[T]) Pop

func (h *Heap[T]) Pop() T

Pop removes and returns the top element from the heap. For min heaps, this is the smallest element. For max heaps, this is the largest element. Panics if the heap is empty.

func (*Heap[T]) Push

func (h *Heap[T]) Push(x T)

Push adds an element to the heap. The heap property is maintained after the operation.

func (*Heap[T]) Remove

func (h *Heap[T]) Remove(i int) T

Remove removes and returns the element at index i. The heap property is maintained after the operation. Panics if i is out of range.

func (*Heap[T]) Snapshot

func (h *Heap[T]) Snapshot() []T

Snapshot returns a copy of the heap's current elements. The returned slice is independent of the heap and can be safely modified.

type LesserThanable

type LesserThanable[T any] interface {
	// LesserThan returns true if the current value is less than the given value.
	LesserThan(T) bool
}

LesserThanable represents types that can be compared with "less than" operation. Types implementing this interface can be used in min heaps.