unionfind

Documentation

Index

• type Node
  • func NewNode(value interface{}, rank int, parent *Node) *Node
  • func (node *Node) GetRank() int
  • func (node *Node) GetValue() interface{}
• type UnionFind
  • func NewUnionFind() *UnionFind
  • func (union *UnionFind) FindInSet(value interface{}) *Node
  • func (union *UnionFind) Has(value interface{}) bool
  • func (union *UnionFind) Union(value1 interface{}, value2 interface{}) *Node

Types

type Node

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

func NewNode

func NewNode(value interface{}, rank int, parent *Node) *Node

func (*Node) GetRank

func (node *Node) GetRank() int

Get Node rank Returns rank O(1) time, O(1) space

func (*Node) GetValue

func (node *Node) GetValue() interface{}

Get Node value Returns value O(1) time, O(1) space

type UnionFind

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

func NewUnionFind

func NewUnionFind() *UnionFind

func (*UnionFind) FindInSet

func (union *UnionFind) FindInSet(value interface{}) *Node

Get parent node of the union searching by value of its member Return union's parent Node O(m) time, O(1) space (in the worst case O(m), where m is the number of Union calls)

func (*UnionFind) Has

func (union *UnionFind) Has(value interface{}) bool

Check if UnionFind has union for specific value Return true if union exists O(1) time, O(1) space

func (*UnionFind) Union

func (union *UnionFind) Union(value1 interface{}, value2 interface{}) *Node

Join two unions using any values belonging to them Return new union's parent Node O(m*a(n)) time, O(m) space (approximately O(m), where m is the number of calls, a(n) is the inverse Ackermann function)