heap

Documentation

Index

• type Comparer
• type MinDHeap
  • func New(degree int, elems ...*Node) *MinDHeap
  • func (m *MinDHeap) Contains(elm int) bool
  • func (m *MinDHeap) Heapify(arr []*Node)
  • func (m *MinDHeap) Insert(n *Node)
  • func (m *MinDHeap) IsEmpty() bool
  • func (m *MinDHeap) Peek() *Node
  • func (m *MinDHeap) Poll() (*Node, bool)
  • func (m *MinDHeap) PrintHeap()
  • func (m *MinDHeap) RemoveAt(idxToRemove int) *Node
  • func (m *MinDHeap) Sink(idx int)
  • func (m *MinDHeap) Size() int
  • func (m *MinDHeap) Swim(idx int)
• type MinHeap
  • func NewMinHeap(elems ...*Node) *MinHeap
  • func (m *MinHeap) Contains(elm int) bool
  • func (m *MinHeap) Heapify(arr []*Node)
  • func (m *MinHeap) Insert(n *Node)
  • func (m *MinHeap) Left(idx int) int
  • func (m *MinHeap) Parent(idx int) int
  • func (m *MinHeap) Peek() *Node
  • func (m *MinHeap) Poll() (*Node, bool)
  • func (m *MinHeap) PrintHeap()
  • func (m *MinHeap) RemoveAt(idx int) *Node
  • func (m *MinHeap) Right(idx int) int
  • func (m *MinHeap) Sink(idx int)
  • func (m *MinHeap) Swap(idx1, idx2 int)
  • func (m *MinHeap) Swim(idx int)
• type Node
  • func NewNode(Value, Weight int) (n *Node)
  • func (a *Node) Compare(b *Node) int

Types

type Comparer

type Comparer interface {
	Compare(b Node) int
}

Comparer interface that provides method signature for Compare

type MinDHeap

type MinDHeap struct {
	// contains filtered or unexported fields
}

MinDHeap struct

func New

func New(degree int, elems ...*Node) *MinDHeap

NewMinHeap creates new minHeap O(n) using heapify()

func (*MinDHeap) Contains

func (m *MinDHeap) Contains(elm int) bool

func (*MinDHeap) Heapify

func (m *MinDHeap) Heapify(arr []*Node)

func (*MinDHeap) Insert

func (m *MinDHeap) Insert(n *Node)

Insert ...

func (*MinDHeap) IsEmpty

func (m *MinDHeap) IsEmpty() bool

IsEmpty ...

func (*MinDHeap) Peek

func (m *MinDHeap) Peek() *Node

func (*MinDHeap) Poll

func (m *MinDHeap) Poll() (*Node, bool)

func (*MinDHeap) PrintHeap

func (m *MinDHeap) PrintHeap()

PrintHeap prints the heap

func (*MinDHeap) RemoveAt

func (m *MinDHeap) RemoveAt(idxToRemove int) *Node

func (*MinDHeap) Sink

func (m *MinDHeap) Sink(idx int)

func (*MinDHeap) Size

func (m *MinDHeap) Size() int

Size returns heap size

func (*MinDHeap) Swim

func (m *MinDHeap) Swim(idx int)

type MinHeap

type MinHeap struct {
	Heap []*Node
	Size int
}

MinHeap struct

func NewMinHeap

func NewMinHeap(elems ...*Node) *MinHeap

NewMinHeap creates new minHeap O(n) using heapify()

func (*MinHeap) Contains

func (m *MinHeap) Contains(elm int) bool

Contains checks if element in heap

func (*MinHeap) Heapify

func (m *MinHeap) Heapify(arr []*Node)

Heapify builds the heap using nodes O(n)

func (*MinHeap) Insert

func (m *MinHeap) Insert(n *Node)

Insert element, while maintaining heap invariant O(log n)

func (*MinHeap) Left

func (m *MinHeap) Left(idx int) int

Left returns left child idx

func (*MinHeap) Parent

func (m *MinHeap) Parent(idx int) int

Parent returns parent index

func (*MinHeap) Peek

func (m *MinHeap) Peek() *Node

Peek returns top most element in heap O(1)

func (*MinHeap) Poll

func (m *MinHeap) Poll() (*Node, bool)

Poll returns and removes the top most element in heap O(log n)

func (*MinHeap) PrintHeap

func (m *MinHeap) PrintHeap()

PrintHeap prints the heap

func (*MinHeap) RemoveAt

func (m *MinHeap) RemoveAt(idx int) *Node

RemoveAt removes element at index O(log n)

func (*MinHeap) Right

func (m *MinHeap) Right(idx int) int

Right returns right child idx

func (*MinHeap) Sink

func (m *MinHeap) Sink(idx int)

Sink bubbles down item O(log n)

func (*MinHeap) Swap

func (m *MinHeap) Swap(idx1, idx2 int)

Swap swaps idxs

func (*MinHeap) Swim

func (m *MinHeap) Swim(idx int)

Swim bubbles up an element until heap invariant is satisfied O(log n)

type Node

type Node struct {
	Weight, Value int
}

Node contains Weight and Value

func NewNode

func NewNode(Value, Weight int) (n *Node)

NewNode creates new node

func (*Node) Compare

func (a *Node) Compare(b *Node) int

Compare method to check equality of two nodes based on weight