heap

Documentation

Index

• type Heap
  • func (h *Heap[T]) Init(d []T)
  • func (h *Heap[T]) Len() int
  • func (h *Heap[T]) Max() T
  • func (h *Heap[T]) Min() T
  • func (h *Heap[T]) Pop() T
  • func (h *Heap[T]) PopLast() T
  • func (h *Heap[T]) Push(x T)
  • func (h *Heap[T]) Remove(i int) T
  • func (h *Heap[T]) Slice() []T
• type Lessable

Types

type Heap

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

Heap represents the heap data structure using a flat array to store the elements. It is a wrapper around the standard library's heap.

func (*Heap[T]) Init

func (h *Heap[T]) Init(d []T)

Init establishes the heap invariants required by the other routines in this package. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. The complexity is O(n) where n = h.Len().

func (*Heap[T]) Len

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

Len returns the number of elements in the heap.

func (*Heap[T]) Max

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

Max returns the maximum element in the heap.

func (*Heap[T]) Min

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

Min returns the minimum element in the heap.

func (*Heap[T]) Pop

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

Pop removes and returns the minimum element (according to Less) from the heap. The complexity is O(log n) where n = h.Len(). Pop is equivalent to Remove(h, 0).

func (*Heap[T]) PopLast

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

func (*Heap[T]) Push

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

Push pushes the element x onto the heap. The complexity is O(log n) where n = h.Len().

func (*Heap[T]) Remove

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

Remove removes and returns the element at index i from the heap. The complexity is O(log n) where n = h.Len().

func (*Heap[T]) Slice

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

type Lessable

type Lessable[T any] interface {
	Less(T) bool
}

Lessable is an interface that allows a type to be compared to another of the same type. It is used to define the order of elements in the heap.