Documentation ¶
Overview ¶
Package heapordered provides Tree: a generic min-heap-ordered tree.
Index ¶
- type Tree
- func (n *Tree[E]) At(i int) *Tree[E]
- func (n *Tree[E]) Down()
- func (n *Tree[E]) EachChild(f func(*Tree[E]))
- func (n *Tree[E]) Fix()
- func (n *Tree[E]) Grow(cap int)
- func (n *Tree[E]) Init()
- func (n *Tree[E]) Len() int
- func (n *Tree[E]) Min() *Tree[E]
- func (parent *Tree[E]) NewChild(e E, priority float64) *Tree[E]
- func (parent *Tree[E]) NewChildTree(n *Tree[E])
- func (n *Tree[E]) Parent() *Tree[E]
- func (n *Tree[E]) Pop() (min *Tree[E])
- func (n *Tree[E]) Remove()
- func (n *Tree[E]) UpdatePriority(v float64) (oldValue float64)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree[E any] struct { // Priority value for the node. // // Fix, Down or UpdatePriority should be called when the Prioirty value changes. Priority float64 // E is a generic element payload. E E // contains filtered or unexported fields }
Tree represents a node in the tree among heap-ordered children.
Tree keeps track of its own index in the child slice so we can call Fix when the Priority changes.
func NewTree ¶
NewTree creates a new tree node with children.
NewTree initializes a heap for the children.
func (*Tree[E]) Down ¶
func (n *Tree[E]) Down()
Down repairs the heap property when the priority value has increased.
Fix or ReplaceElem should be called when the node's Prioirty value changes.
func (*Tree[E]) Fix ¶
func (n *Tree[E]) Fix()
Fix repairs the heap property for the current node in the parent's child heap.
Fix or ReplaceElem should be called when the node's Prioirty value changes.
func (*Tree[E]) NewChild ¶
NewChild creates a new child node in the parent.
NewChild places the child on the heap.
func (*Tree[E]) NewChildTree ¶
NewChild creates a new child node in the parent.
NewChild places the child on the heap.
func (*Tree[E]) Pop ¶
Pop removes the best node from the child heap.
Pop panics if n has no children.
func (*Tree[E]) Remove ¶
func (n *Tree[E]) Remove()
Remove the current node from the parent's child heap.
Remove panics if n is not part of a parent heap.
func (*Tree[E]) UpdatePriority ¶
UpdatePriority replaces the priority for the current node and calls Fix to repair the heap property. Returns the old element.