A Scala version of the weighted quick-union algorithm from Sedgewick’s Coursera Algorithms class

WeightedQuickUnion.scala

val unions = Seq(4->3, 3->8, 6->5, 9->4, 2->1, 5->0, 7->2, 6->1, 1->0)
val parents = (0 to 9).toArray
val depths = Array.fill(10)(1)

def connected(p: Int, q: Int) = root(p) == root(q)

def union(p: Int, q: Int) {
  val i = root(p)
  val j = root(q)
  val (sm, lg) = if (depths(i) < depths(j)) (i, j) else (j, i)
  parents(sm) = lg
  println("%d moved under %d".format(sm, lg))
  depths(lg) += depths(sm)
}

private def showArrays() {
  Seq(parents, depths).foreach(a =>
    println(a.mkString(" "))
  )
}

private def root(n: Int): Int = if (parents(n) == n) n else root(parents(n))

showArrays()
unions.foreach {
  case (p, q) =>
    println("%d-%d".format(p, q))
    union(p, q)
    showArrays()
}