5 people like it.

# Weighted Quick-Union with Path Compression

Implementation of Mutable Weighted Quick-Union with Path Compression in F#

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: ``` ``````// 06-09-2011 Edit: sz array was initialized to be all 0 instead of 1 // From Wikipedia: http://en.wikipedia.org/wiki/Disjoint-set_data_structure // In computing, a disjoint-set data structure is a data structure that keeps track // of a set of elements partitioned into a number of disjoint (nonoverlapping) // subsets. A union-find algorithm is an algorithm that performs two useful // operations on such a data structure: // Find: Determine which set a particular element is in. Also useful for // determining if two elements are in the same set. // Union: Combine or merge two sets into a single set. // Implementation from: http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf /// Quick-find... Union is O(N), Flat Trees /// Quick-union... Trees are tall, Find is O(N), Find requires union /// Overall: O(MN) -- M union-find ops on a set of N objects type QuickUnion (N) = //Parent index, id[i] is parent of i let mutable id : int[] = Array.init N (fun i -> i) let root i = let mutable q = i while (q <> id.[q]) do q <- id.[q] q member t.find(p, q) = root(p) = root(q) member t.unite(p, q) = let i = root(p) let j = root(q) id.[i] = j; /// Weighted QuickUnion /// Now with logN union, lgN find /// Overall: O(N+MLogN) -- M union-find ops on a set of N objects type WeightedQuickUnion (N) = //Parent index, id[i] is parent of i let id : int[] = Array.init N (fun i -> i) //Number of elements rooted at i let sz : int[] = Array.create N 1 let root i = let mutable q = i while (q <> id.[q]) do q <- id.[q] q member t.find(p, q) = root(p) = root(q) member t.unite(p, q) = let i = root(p) let j = root(q) if sz.[i] < sz.[j] then id.[i] <- j; sz.[j] <- sz.[j] + sz.[i] else id.[j] <- i; sz.[i] <- sz.[i] + sz.[j] /// Weighted quick-union with path compression /// Overall: O((M+N)lg*N) -- M union-find ops on a set of N objects type QuickUWPC (N) = //Parent index, id[i] is parent of i let id : int[] = Array.init N (fun i -> i) //Number of elements rooted at i let sz : int[] = Array.create N 1 let root i = let mutable q = i while (q <> id.[q]) do id.[q] <- id.[id.[q]] q <- id.[q] q member t.find(p, q) = root(p) = root(q) member t.unite(p, q) = let i = root(p) let j = root(q) if sz.[i] < sz.[j] then id.[i] <- j; sz.[j] <- sz.[j] + sz.[i] else id.[j] <- i; sz.[i] <- sz.[i] + sz.[j] ``````
Multiple items
type QuickUnion =
new : N:int -> QuickUnion
member find : p:int * q:int -> bool
member unite : p:int * q:int -> bool

Full name: Script.QuickUnion

Quick-find... Union is O(N), Flat Trees
Quick-union... Trees are tall, Find is O(N), Find requires union
Overall: O(MN) -- M union-find ops on a set of N objects

--------------------
new : N:int -> QuickUnion
val N : int
val mutable id : int []
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
module Array

from Microsoft.FSharp.Collections
val init : count:int -> initializer:(int -> 'T) -> 'T []

Full name: Microsoft.FSharp.Collections.Array.init
val i : int
val root : (int -> int)
val mutable q : int
val t : QuickUnion
member QuickUnion.find : p:int * q:int -> bool

Full name: Script.QuickUnion.find
val p : int
val q : int
member QuickUnion.unite : p:int * q:int -> bool

Full name: Script.QuickUnion.unite
val j : int
Multiple items
type WeightedQuickUnion =
new : N:int -> WeightedQuickUnion
member find : p:int * q:int -> bool
member unite : p:int * q:int -> unit

Full name: Script.WeightedQuickUnion

Weighted QuickUnion
Now with logN union, lgN find
Overall: O(N+MLogN) -- M union-find ops on a set of N objects

--------------------
new : N:int -> WeightedQuickUnion
val id : int []
val sz : int []
val create : count:int -> value:'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create
val t : WeightedQuickUnion
member WeightedQuickUnion.find : p:int * q:int -> bool

Full name: Script.WeightedQuickUnion.find
member WeightedQuickUnion.unite : p:int * q:int -> unit

Full name: Script.WeightedQuickUnion.unite
Multiple items
type QuickUWPC =
new : N:int -> QuickUWPC
member find : p:int * q:int -> bool
member unite : p:int * q:int -> unit

Full name: Script.QuickUWPC

Weighted quick-union with path compression
Overall: O((M+N)lg*N) -- M union-find ops on a set of N objects

--------------------
new : N:int -> QuickUWPC
val t : QuickUWPC
member QuickUWPC.find : p:int * q:int -> bool

Full name: Script.QuickUWPC.find
member QuickUWPC.unite : p:int * q:int -> unit

Full name: Script.QuickUWPC.unite