heap

Documentation

Index

• type Entry
• type Heap
  • func New[I any, V constraints.Ordered](items int, isMinHeap bool) *Heap[I, V]
  • func (h *Heap[I, V]) First() *Entry[I, V]
  • func (h *Heap[I, V]) Get(id ids.ID) (*Entry[I, V], bool)
  • func (h *Heap[I, V]) Has(id ids.ID) bool
  • func (h *Heap[I, V]) Items() []*Entry[I, V]
  • func (h *Heap[I, V]) Len() int
  • func (h *Heap[I, V]) Pop() *Entry[I, V]
  • func (h *Heap[I, V]) Push(e *Entry[I, V])
  • func (h *Heap[I, V]) Remove(index int) *Entry[I, V]

Types

type Entry

type Entry[I any, V constraints.Ordered] struct {
	ID   ids.ID // id of entry
	Item I      // associated item
	Val  V      // Value to be prioritized

	Index int // Index of the entry in heap
}

type Heap

type Heap[I any, V constraints.Ordered] struct {
	// contains filtered or unexported fields
}

Heap[I,V] is used to track objects of [I] by [Val].

This data structure does not perform any synchronization and is not safe to use concurrently without external locking.

func New

func New[I any, V constraints.Ordered](items int, isMinHeap bool) *Heap[I, V]

New returns an instance of Heap[I,V]

func (*Heap[I, V]) First

func (h *Heap[I, V]) First() *Entry[I, V]

First returns the first item in the heap. This is the smallest item in a minHeap and the largest item in a maxHeap.

If no items are in the heap, it will return nil.

func (*Heap[I, V]) Get

func (h *Heap[I, V]) Get(id ids.ID) (*Entry[I, V], bool)

Get returns the entry in th associated with [id], and a bool if [id] was found in th.

func (*Heap[I, V]) Has

func (h *Heap[I, V]) Has(id ids.ID) bool

Has returns whether [id] is found in th.

func (*Heap[I, V]) Items

func (h *Heap[I, V]) Items() []*Entry[I, V]

Items returns all items in the heap in sorted order. You should not modify the response.

func (*Heap[I, V]) Len

func (h *Heap[I, V]) Len() int

Len returns the number of items in ih.

func (*Heap[I, V]) Pop

func (h *Heap[I, V]) Pop() *Entry[I, V]

Pop can be called by external users to remove an object from the heap at a specific index instead of using `containers.heap`, which makes using this heap less error-prone.

func (*Heap[I, V]) Push

func (h *Heap[I, V]) Push(e *Entry[I, V])

Push can be called by external users instead of using `containers.heap`, which makes using this heap less error-prone.

func (*Heap[I, V]) Remove

func (h *Heap[I, V]) Remove(index int) *Entry[I, V]

Remove can be called by external users to remove an object from the heap at a specific index instead of using `containers.heap`, which makes using this heap less error-prone.