scala - Scala 中的 Union-Find(或 Disjoint Set)数据结构

Question

在我尝试推出自己的优化之前，我正在寻找 Scala 中联合查找或不相交集数据结构的现有实现，因为优化看起来有些复杂。

我是说 this类似的东西 - union 和 find 这两个操作被优化了。

有人知道任何现存的东西吗？我显然尝试过谷歌搜索。

Answer 1

前段时间我为自己写了一个我认为表现不错的。与其他实现不同，find 是 O(1) 而 union 是 O(log(n))。如果您有比 find 更多的 union 操作，那么这可能不是很有用。我希望你觉得它有用:

package week2

import scala.collection.immutable.HashSet
import scala.collection.immutable.HashMap

/**
 * Union Find implementaion.
 * Find is O(1)
 * Union is O(log(n))
 * Implementation is using a HashTable. Each wrap has a set which maintains the elements in that wrap.
 * When 2 wraps are union, then both the set's are clubbed. O(log(n)) operation
 * A HashMap is also maintained to find the Wrap associated with each node. O(log(n)) operation in mainitaining it.
 * 
 * If the input array is null at any index, it is ignored
 */
class UnionFind[T](all: Array[T]) {
  private var dataStruc = new HashMap[T, Wrap]
  for (a <- all if (a != null))
    dataStruc = dataStruc + (a -> new Wrap(a))

  var timeU = 0L
  var timeF = 0L

  /**
   * The number of Unions
   */
  private var size = dataStruc.size

  /**
   * Unions the set containing a and b
   */
  def union(a: T, b: T): Wrap = {
    val st = System.currentTimeMillis()
    val first: Wrap = dataStruc.get(a).get
    val second: Wrap = dataStruc.get(b).get
    if (first.contains(b) || second.contains(a))
      first
    else {
      // below is to merge smaller with bigger rather than other way around
      val firstIsBig = (first.set.size > second.set.size)
      val ans = if (firstIsBig) {
        first.set = first.set ++ second.set
        second.set.foreach(a => {
          dataStruc = dataStruc - a
          dataStruc = dataStruc + (a -> first)
        })
        first
      } else {
        second.set = second.set ++ first.set
        first.set.foreach(a => {
          dataStruc = dataStruc - a
          dataStruc = dataStruc + (a -> second)
        })
        second
      }
      timeU = timeU + (System.currentTimeMillis() - st)
      size = size - 1
      ans
    }
  }

  /**
   * true if they are in same set. false if not
   */
  def find(a: T, b: T): Boolean = {
    val st = System.currentTimeMillis()
    val ans = dataStruc.get(a).get.contains(b)
    timeF = timeF + (System.currentTimeMillis() - st)
    ans
  }

  def sizeUnion: Int = size

  class Wrap(e: T) {
    var set = new HashSet[T]
    set = set + e

    def add(elem: T) {
      set = set + elem
    }

    def contains(elem: T): Boolean = set.contains(elem)
  }
}