uf

Documentation

Index

• type QuickFind
  • func NewQuickFind(n int) *QuickFind
  • func (qf *QuickFind) Find(i, j int) bool
  • func (qf *QuickFind) Union(i, j int)
• type QuickUnion
  • func NewQuickUnion(n int) *QuickUnion
  • func (qu *QuickUnion) Find(i, j int) bool
  • func (qu *QuickUnion) Union(i, j int)
• type UnionFind
• type WQUPC
  • func NewWQUPC(n int) *WQUPC
  • func (qu *WQUPC) Find(i, j int) bool
  • func (qu *WQUPC) Root(i int) int
  • func (qu *WQUPC) Union(i, j int)
• type WeightedQuickUnion
  • func NewWeightedQuickUnion(n int) *WeightedQuickUnion
  • func (qu *WeightedQuickUnion) Find(i, j int) bool
  • func (qu *WeightedQuickUnion) Union(i, j int)

Types

type QuickFind

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

QuickFind M union-find ops on a N objects worst time complexity is O(MN)

func NewQuickFind

func NewQuickFind(n int) *QuickFind

func (*QuickFind) Find

func (qf *QuickFind) Find(i, j int) bool

Find time complexity O(1)

func (*QuickFind) Union

func (qf *QuickFind) Union(i, j int)

Union time complexity O(N)

type QuickUnion

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

QuickUnion M union-find ops on a N Objects worst time complexity is O(MN)

func NewQuickUnion

func NewQuickUnion(n int) *QuickUnion

QuickUnion is also slow, tree is not flat

func (*QuickUnion) Find

func (qu *QuickUnion) Find(i, j int) bool

Find time complexity proportional to depth of i/j worst case O(N)

func (*QuickUnion) Union

func (qu *QuickUnion) Union(i, j int)

Union just like Find, time complexity Worst Case O(N)

type UnionFind

type UnionFind interface {
	Union(i, j int)
	Find(i, j int) bool
}

type WQUPC

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

WQUPC M union-find ops on a N objects worst time complexity is o((N+M)*lgN)

func NewWQUPC

func NewWQUPC(n int) *WQUPC

func (*WQUPC) Find

func (qu *WQUPC) Find(i, j int) bool

Find time complexity proportional to depth of i/j, depth is at most lgN worst case O(lgN)

func (*WQUPC) Root

func (qu *WQUPC) Root(i int) int

func (*WQUPC) Union

func (qu *WQUPC) Union(i, j int)

Union just like Find, time complexity Worst Case O(lgN)

type WeightedQuickUnion

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

WeightedQuickUnion M union-find ops on a N objects worst time complexity is o(N+MlgN)

func NewWeightedQuickUnion

func NewWeightedQuickUnion(n int) *WeightedQuickUnion

func (*WeightedQuickUnion) Find

func (qu *WeightedQuickUnion) Find(i, j int) bool

Find time complexity proportional to depth of i/j, depth is at most lgN worst case O(lgN)

func (*WeightedQuickUnion) Union

func (qu *WeightedQuickUnion) Union(i, j int)

Union just like Find, time complexity Worst Case O(lgN)