Scala中的Union-Find（或Disjoint Set）數據結構

Question

在我嘗試滾動自己的優化看起來有些複雜之前，我正在尋找Scala中的union-find或disjoint set數據結構的現有實現。

我的意思是this類的東西 - 其中兩個操作union和find進行了優化。

有人知道任何東西存在嗎？我顯然嘗試了Google搜索。

Answer 1

我曾經爲自己寫過一篇我認爲表現不錯的作品。與其他實現不同，find是O(1)和union是O(log(n))。如果您有更多的union操作比find，那麼這可能不是很有用。我希望你覺得它有用：

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) 

    } 

} 

我