heap

README

go-heap

Package heap implements a generic heap data structure.

License

MIT

Documentation

Overview

Package heaps implements a generic heap data structure.

Index

• func PriorityChannel[T any](inCh <-chan T, lessFunc func(T, T) bool) <-chan T
• type Heap
  • func NewHeap[T any](lessFunc func(T, T) bool) *Heap[T]
  • func NewOrderedHeap[T cmp.Ordered]() *Heap[T]
  • func NewReverseOrderedHeap[T cmp.Ordered]() *Heap[T]
  • func (h *Heap[T]) All() iter.Seq[T]
  • func (h *Heap[T]) Cap() int
  • func (h *Heap[T]) Clip() *Heap[T]
  • func (h *Heap[T]) Empty() bool
  • func (h *Heap[T]) Grow(n int) *Heap[T]
  • func (h *Heap[T]) Len() int
  • func (h *Heap[T]) MustPop() T
  • func (h *Heap[T]) Peek() (T, bool)
  • func (h *Heap[T]) Pop() (T, bool)
  • func (h *Heap[T]) PopAll() []T
  • func (h *Heap[T]) Push(value T) *Heap[T]
  • func (h *Heap[T]) PushMany(values ...T) *Heap[T]
  • func (h *Heap[T]) PushPop(value T) T
  • func (h *Heap[T]) Set(values []T) *Heap[T]

Functions

func PriorityChannel

func PriorityChannel[T any](inCh <-chan T, lessFunc func(T, T) bool) <-chan T

PriorityChannel greedily reads values from inCh and returns a channel that returns the same values prioritized according to lessFunc, with lesser values returned first. When inCh is closed, all remaining values are written to the returned channel, and then the returned channel is closed.

Types

type Heap

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

A Heap is a heap of Ts.

func NewHeap

func NewHeap[T any](lessFunc func(T, T) bool) *Heap[T]

NewHeap returns a new heap that uses lessFunc to compare elements.

func NewOrderedHeap

func NewOrderedHeap[T cmp.Ordered]() *Heap[T]

NewOrderedHeap returns a new heap that operates on cmp.Ordered elements.

func NewReverseOrderedHeap

func NewReverseOrderedHeap[T cmp.Ordered]() *Heap[T]

NewReverseOrderedHeap returns a new heap that operates on cmp.Ordered elements in reverse order.

func (*Heap[T]) All

func (h *Heap[T]) All() iter.Seq[T]

All returns an iterator over all values in h.

func (*Heap[T]) Cap

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

Cap returns the underlying capacity of h.

func (*Heap[T]) Clip

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

Clip removes unused capacity from h.

func (*Heap[T]) Empty

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

Empty returns whether h is empty in O(1) time and memory.

func (*Heap[T]) Grow

func (h *Heap[T]) Grow(n int) *Heap[T]

Grow increases h's capacity by at least n.

func (*Heap[T]) Len

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

Len returns the size of h in O(1) time and memory.

func (*Heap[T]) MustPop

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

MustPop returns the lowest value in h. It panics if h is empty.

func (*Heap[T]) Peek

func (h *Heap[T]) Peek() (T, bool)

Peek returns the lowest value in h in O(1) time and memory, without removing it, and whether it exists.

func (*Heap[T]) Pop

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

Pop returns the lowest value in h, removing it, and whether it exists in O(N) time and O(1) memory.

func (*Heap[T]) PopAll

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

PopAll pops and returns all values in h.

func (*Heap[T]) Push

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

Push adds value to h in amortized O(N) time.

func (*Heap[T]) PushMany

func (h *Heap[T]) PushMany(values ...T) *Heap[T]

PushMany pushes multiple values onto the heap.

func (*Heap[T]) PushPop

func (h *Heap[T]) PushPop(value T) T

PushPop pushes value onto the heap and then pops the lowest value off the heap and returns it in O(N) time. It is slightly more efficient than separate calls to Heap.Push and Heap.Pop.

func (*Heap[T]) Set

func (h *Heap[T]) Set(values []T) *Heap[T]

Set sets the values on h to be values in amortized O(N) time. h takes ownership of values.