【從蛋殼到滿天飛】JS 資料結構解析和演算法實現-並查集（一）

摘要： 【從蛋殼到滿天飛】JS 資料結構解析和演算法實現，全部文章大概的內容如下： Arrays(陣列)、Stacks(棧)、Queues(佇列)、LinkedList(連結串列)、Recursion(遞迴思想)、BinarySearchTree(二分搜尋樹)、Set(集合)、Map(對映)、Heap...

【從蛋殼到滿天飛】JS 資料結構解析和演算法實現，全部文章大概的內容如下： Arrays(陣列)、Stacks(棧)、Queues(佇列)、LinkedList(連結串列)、Recursion(遞迴思想)、BinarySearchTree(二分搜尋樹)、Set(集合)、Map(對映)、Heap(堆)、PriorityQueue(優先佇列)、SegmentTree(線段樹)、Trie(字典樹)、UnionFind(並查集)、AVLTree(AVL 平衡樹)、RedBlackTree(紅黑平衡樹)、HashTable(雜湊表)

原始碼有三個：ES6（單個單個的 class 型別的 js 檔案） | JS + HTML（一個 js 配合一個 html）| JAVA (一個一個的工程)

全部原始碼已上傳 github，點選我吧 ，光看文章能夠掌握兩成，動手敲程式碼、動腦思考、畫圖才可以掌握八成。

本文章適合 對資料結構想了解並且感興趣的人群，文章風格一如既往如此，就覺得手機上看起來比較方便，這樣顯得比較有條理，整理這些筆記加原始碼，時間跨度也算將近半年時間了，希望對想學習資料結構的人或者正在學習資料結構的人群有幫助。

並查集 Union Find

1. 並查集是一種很不一樣的樹形結構
   1. 之前的樹結構都是由父親指向孩子，
   2. 但是並查集是由孩子指向父親而形成的這樣的一種樹結構，
   3. 這樣一種奇怪的樹結構可以非常高效的來解決某一類問題，
   4. 這類問題就是連線問題(Connectivity Problem)，
   5. 並查集是一種可以高效的回答連線問題的這樣的一種資料結構。
2. 連線問題
   1. 給出一個圖中任意的兩點，
   2. 這兩點之間是否可以通過一個路徑連線起來，
   3. 簡單的使用肉眼觀察距離很近的兩點，是可以觀察出來的，
   4. 如果兩點的距離很遠，兩點之間隔著還有無數個點，
   5. 那麼你就很難用肉眼觀察出來它們是否是相連的，
   6. 此時就需要藉助一定的資料結構，
   7. 而並查集就是回答這種連線問題一個非常好一種資料結構。
3. 並查集可以非常快的判斷網路中節點的連線狀態
   1. 這裡的網路實際上是一個抽象的概念，
   2. 不僅僅是在計算機領域所使用的網際網路這樣的一個網路，
   3. 最典型的一個例子，如社交網路、微博、微信、facebook，
   4. 他們之間其實就是由一個一個的人作為節點形成的一個網路，
   5. 在這種時候就可以把每兩個使用者之間是不是好友關係，
   6. 這樣的一個概念給抽象成兩個節點之間的邊，
   7. 如果可以這樣的建立一個網路的話，相應的就會產生連線問題，
   8. 比如兩個使用者 A 和 B，他們本來可能是互不認識的，
   9. 那麼通過這個網路是否有可能通過認識的人他認識的人，
   10. 這樣一點點的擴散，最終接觸到那個你本來完全不認識的人，
   11. 這樣的一個問題其實就是在社交網路中相應的連線問題。
4. 網路這樣的一種結構不僅僅是用在社交網路
   1. 很多資訊網路，比如說亞馬遜的商品、豆瓣兒的圖書、
   2. 或者音樂網站的一些音樂專輯，這些內容都可以形成節點，
   3. 節點之間都可以以某種形式來定義邊，從而形成一個巨大的網路，
   4. 可以在這樣的網路中做非常多的事情，
   5. 比如交通系統、公交車、火車、飛機等航班與航線之間他們全都是網路，
   6. 更不用提計算機的網路，每一個路由器都是一個節點，
   7. 其實網路本身是一個應用非常廣泛的概念，
   8. 在實際中處理的很多問題，把它抽象出來可能都是一個網路上的問題，
5. 在回答網路中的節點的連線狀態這樣的一個問題的時候，
   1. 並查集就是一個非常強力的效能非常高效的資料結構，
   2. 並查集除了可以高效的回答網路中節點間的連線狀態的問題之外，
   3. 還是數學中集合這種類的一個很好的實現，
   4. 如果你使用的集合主要的操作是在求兩個集合的並集的時候，
   5. 並查集中並 其實就是集合中的並 這樣的概念，
   6. 相應的查就是一個查詢操作。
6. 對於並查集來說他們非常高效的來回答在網路中兩個節點是否連線的問題
   1. 在一個網路也是可以兩個節點他們之間的路徑是怎樣的，
   2. 既然可以求出兩個節點之間的路徑，其實就回答了連線的問題，
   3. 兩個節點之間如果存在一個路徑，那麼就一定是連線的，
   4. 如果這個路徑根本就不存在，那麼它肯定是不連線的，
   5. 這樣的一個思路肯定是正確的，
   6. 如果想要回答兩個節點之間的連線問題，
   7. 這個答案其實是比回答兩個節點之間的路徑問題回答的內容要少的，
   8. 因為只需要返回 true 或者 false 就好了，
   9. 但是如果要問 A 和 B 之間的路徑是什麼的話，
   10. 那麼相應的就要得到一個從 A 節點出發一步一步達到節點 B，
   11. 這樣一個具體的路徑，換句話說其實回答路徑問題的方式
   12. 來回答連線問題，那麼真正回答的內容是更加的多了，
   13. 這樣會導致結果消耗了一些額外的效能求出了當前不關心的內容，
   14. 那個內容就是 A 和 B 之間的具體路徑是什麼。
7. 當你深入的學習資料結構和演算法

   O(n)
   

8. 連線問題和路徑問題也是一樣的
   1. 雖然可以使用求解路徑的思路來看 A 和 B 這兩個點是否連線，
   2. 但是由於它回答了額外的問題，A 和 B 之間具體怎麼連線都回答出來了，
   3. 在很多時候並不關心 A 和 B 之間怎麼連線，只要看他是否連線，
   4. 此時並查集就是一種更好的選擇，對於這一點，
   5. 很多演算法或者資料結構它們所解決的問題之間的差別是非常微妙的，
   6. 需要不斷的積累不斷的實踐，慢慢的瞭解每種不同的演算法或者不同的資料結構，
   7. 它們所解決的那個問題以及具體的不同點在哪裡，
   8. 時間久了就可以慢慢的非常快速的反應出對於某一些具體問題
   9. 最好的應該使用哪種演算法或者哪種資料結構來進行解決。
9. 具體來講對於並查集這種資料結構來說

   union(p, q)
   isConnected(p, q)
   

10. 需要設計這樣的一種並查集介面
    1. 也就是說並查集也可以有不同的底層實現，
    2. 通過實現不同的並查集，
    3. 可以一點點的優化自己實現的並查集，
    4. 隨著你不斷的優化，
    5. 自己編寫的這個並查集在具體的解決連線問題的時候，
    6. 效率會越來越高。

並查集 簡單實現

1. MyUnionFind

   unionElements(p, q)
   isConnected(p, q)
   getSize()
   

2. isConnected 方法中傳入的 p 和 q 都是 int 型，
   1. 對於具體元素是誰，在並查集的內部並不關心，
   2. 在使用並查集的時候可以將元素和一個數組相對應的陣列索引做一個對映
   3. 相當於真正關心的是一個 id 為 p 和 id 為 q 這樣的兩個元素它們是否相連，
   4. 對於 id 為 p 這樣的元素它具體對應的是什麼樣的一個元素並不關心。
3. unionElements 方法中傳入的 p 和 q 都是 int 型。
4. 向線段樹一樣，並不考慮新增一個元素或者刪除一個元素
   1. 考慮的是對於當下固定的元素來說，
   2. 進行並或者查這樣的兩個操作。

程式碼示例

1. MyUnionFind

   // 自定義並查集 UnionFind
   class MyUnionFind {
   // 功能：將元素q和元素p這兩個資料以及他們所在的集合進行合併
   unionElements(q, p) {}
   
   // 功能：查詢元素q和元素p這兩個資料是否在同一個集合中
   isConnected(q, p) {}
   
   // 功能：當前並查集一共考慮多少個元素
   getSize() {}
   }
   複製程式碼

並查集 簡單實現 Quick Find

1. 對於並查集主要實現兩個操作

   1. union 操作將兩個元素合併在一起變成在一個集合中的元素，
   2. isConnected 操作檢視兩個元素是否是相連的

2. 並查集的基本資料表示

   1. 可以直接給每個資料做一個編號，
   2. 0-9 就表示 10 個不同的資料，
   3. 這是一種抽象的表示，
   4. 具體這十個編號可能是十個人或者是十部車或者是十本書，
   5. 這是由你的業務邏輯所決定的，
   6. 但是在並查集的內部只存 0-9 這是個編號，
   7. 它表示十個具體的元素
   8. 對於每一個元素它儲存的是對應的集合的 ID。
   9. 例如下圖並查集一中編號 0-4 這五個資料它們所對應的 ID 為 0，
   10. 編號為 5-9 這五個資料它們所對應的 ID 為 1，
   11. 不同的 ID 值就是不同的集合所對應的那個編號，
   12. 在並查集中就可以表示為 將這個十個資料分成了兩個集合，
   13. 其中 0-4 這五個元素在一個集合中，5-9 這個五個元素在另一個集合中。
   14. 如果是下圖並查集二中這樣子，
   15. 其中 0、2、4、6、8 這五個元素在一個集合中，
   16. 而 1、3、5、7、9 這五個元素在一個集合中，
   17. 在具體的程式設計中會把這樣的一個數組稱之為 id，
   18. 通過這樣的一個數組就可以非常容易的來回答所謂的連線問題，
   19. 在並查集圖二中，0 和 2 就是相連線的，
   20. 或者說 0 和 2 是同屬於一個集合的，因為他們所對應的 id 的值都是 0，
   21. 1 和 3 也屬於同一個同一個集合，因為他們所對應的 id 值都為 1，
   22. 相應的可以想象 1 和 2 都屬於不同的集合，因為他們對應的 id 值是不同的。

   // 並查集 一
   //0123456789
   //-------------------------------------
   // id0000011111
   
   // 並查集 二
   //0123456789
   //-------------------------------------
   // id0101010101
   複製程式碼

3. 使用 id 這樣的一個數組來儲存你的資料

   1. 是可以很容易的回答 isConnected 的這個問題的，
   2. 只需要直接來看 p 和 q 這兩個值所對應的 id 值是否一樣就好了，
   3. 將查詢 p 或者 q 每個元素背後所對應的那個集合的 id 是誰也
   4. 抽象成一個函式，這個函式就叫做 find，
   5. 只需要看find(p) 是否等於find(q) 就好了。

4. 當你使用 find 函式進行操作的時候只需要O(1) 的時間複雜度

   1. 直接取出 id 這個陣列所對應的這個資料的 Index 相應值即可，
   2. 所以對於這種儲存方式在並查集上進行 find 操作時是非常快速的，
   3. 這種並查集的方式通常稱為 QuickFind，
   4. 也就是對於 find 這種操作運算速度是非常快的。

      // 並查集
      //0123456789
      //-------------------------------------
      // id0101010101
      複製程式碼

5. QuickFind 方式的並查集中實現 union

   union(1, 4)
   union(1, 4)
   O(n)
   

   // 並查集
   //0123456789
   //-------------------------------------
   // id0101010101
   
   // 並查集 union(1, 4)之後的並查集
   //0123456789
   //-------------------------------------
   // id1111111111
   複製程式碼

程式碼示例

1. MyUnionFindOne

   // 自定義並查集 UnionFind 第一個版本 QuickFind版
   // isConnected 操作很快
   class MyUnionFindOne {
   constructor(size) {
   // 儲存資料所對應的集合的編號
   this.ids = new Array(size);
   
   // 模擬存入資料
   const len = this.ids.length;
   for (var i = 0; i < len; i++) this.ids[i] = i;
   }
   
   // 功能：將元素q和元素p這兩個資料以及他們所在的集合進行合併
   // 時間複雜度：O(n)
   unionElements(q, p) {
   const qId = this.find(q);
   const pId = this.find(p);
   
   if (qId === pId) return;
   
   for (var i = 0; i < this.ids.length; i++)
   if (pId === this.ids[i]) this.ids[i] = qId;
   }
   
   // 功能：查詢元素q和元素p這兩個資料是否在同一個集合中
   // 時間複雜度：O(1)
   isConnected(q, p) {
   return this.ids[q] === this.ids[p];
   }
   
   // 查詢元素所對應的集合編號
   find(index) {
   if (index < 0 || index >= this.ids.length)
   throw new Error('index is out of bound.');
   return this.ids[index];
   }
   
   // 功能：當前並查集一共考慮多少個元素
   getSize() {
   return this.ids.length;
   }
   }
   複製程式碼

並查集 簡單實現 Quick Union

1. QuickFind 的方式實現的並查集查詢速度非常快

   1. 但是通常在標準情況下都是使用 QuickUnion 的方式實現並查集。

2. QuickUnion 的方式實現並查集思路

   1. 將每一個元素，看作是一個節點，而節點之間相連線形成了一個樹結構，
   2. 這棵樹和之前實現的所有的樹都不一樣，
   3. 在並查集上實現的樹結構是孩子指向父親，
   4. 例如節點 3 指向節點 2，那麼節點 2 就是這棵樹的根節點，
   5. 雖然節點 2 是一個根節點，但是它也有一個指標，這個指標指向的是自己，
   6. 在這種情況下如果節點 1 要和節點 3 進行一個合併，
   7. 這個合併操作就是就是讓節點 1 的指標指向節點 3 指向的這棵樹的根節點，
   8. 也就是讓節點 1 去指向節點 2。
   9. 如果又有一棵樹 節點 7 和節點 6 都指向節點 5，節點 5 是這棵樹的根節點，
   10. 但是如果要節點 7 要和節點 2 做一下合併，
   11. 其實就是就是讓節點 7 所在的這棵樹的根節點也就是節點 5 去指向節點 2，
   12. 或者你是想讓節點 7 和節點 3 進行一下合併，
   13. 那麼的得到的結果依然是這樣的，因為實際的操作是讓
   14. 節點 7 所在的這棵樹的根節點去指向節點 3 所在的這棵樹的根節點，
   15. 依然是節點 5 去指向節點 2，所以依然得到相同的結果，
   16. 這就是實際實現並查集相應的思路。

   //(5)(2)
   ///\|\
   ///\|\
   // (6)(7)(3)(1)
   複製程式碼

3. QuickUnion 的方式實現並查集非常的簡單

   1. 因為每一個節點本身只有一個指標，只會指向另外一個元素，
   2. 並且這個指標的儲存依然可以使用陣列的方式來儲存，
   3. 這個陣列就叫做 parent，
   4. parent[i]就表示第 i 個元素所在的那個節點它指向了哪個元素，
   5. 雖然說是指標，但是實際儲存的時候依然使用一個 int 型的陣列就夠了，
   6. 這樣一來在初始化的時候parent[i] = i ，
   7. 也就是初始化的時候每一個節點都沒有和其它的節點進行合併，
   8. 所以在初始化的時候每一個節點都指向了自己，
   9. 在這種情況下相當於 以 10 個元素為例，並查集整體就是下圖這樣子，
   10. 每一個節點都是一個根節點，它們都指向自己。
   11. 嚴格的來說這個並查集不是一棵樹結構，而是一個森林，
   12. 所謂的森林就是說裡面有很多的樹，在初始的情況下，
   13. 這個森林中就有 10 棵樹，每棵樹都只有一個節點，
   14. 如果進行union(4, 3) 操作，
   15. 那麼直接讓節點 4 的的指標去指向節點 3 就好了，
   16. 這樣的一個操作在陣列中表示出來就是parent[4] = 3 ，
   17. 那麼節點 4 它指向了節點 3，如果在進行union(3, 8) 操作，
   18. 那麼就讓節點 3 的指標指向的那個元素指向節點 8，
   19. 那麼在陣列中parent[3] = 8 ，再進行union(6, 5) 操作，
   20. 那麼就讓節點 6 的指標指向的那個元素指向節點 5，
   21. 也就是parent[6] = 5 ，再進行union(9, 4) 操作，
   22. 那麼就讓節點 9 的指標指向指向節點 4 這棵樹的根節點，
   23. 那麼在這裡就有一個查詢操作了，
   24. 那麼就要看一下 4 這個節點所在的根節點是誰，
   25. 這個查詢過程就是 節點 4 指向了節點 3，節點 3 又指向了節點 8，
   26. 而節點 8 自己指向了節點 8 也就是指向了自己，說明 8 是一個根節點，
   27. 那麼下面要做的事情就是讓 9 這個節點指向節點 8 就好了
   28. 也就是parent[9] = 8 ，之所以不讓節點 9 指向節點 4，
   29. 因為那樣的話就會形成一個連結串列，那麼樹整體的優勢就體現不出來，
   30. 當你的節點 9 指向節點 8，下次你查詢節點 9 的根節點只需要進行一步查詢，
   31. 所以才讓parent[9] = 8 ，再進行union(2, 1) 操作，
   32. 直接讓節點 2 指向節點 1 就好了，parent[2] = 1 ，
   33. 再進行union(5, 0) 操作，直接讓節點 5 指向節點 0 就好了，
   34. parent[5] = 0 ，再進行union(7, 2) 操作，
   35. 由於節點 2 指向節點 1，那麼節點 7 就要指向節點 1，
   36. parent[7] = 1 。
   37. 接下來進行一個稍微複雜一點的操作，進行union(6, 2) 操作，
   38. 由於節點 6 指向節點 5，而節點 5 指向節點 0，2 指向節點 1，
   39. 那麼就是讓節點 0 指向節點 1 了，所以parent[0] = 1 。
   40. 這樣的一種實現就是並查集通常真正的實現方式。

   //0123456789
   //-------------------------------------
   //parent0123456789
   //
   //Quick Union
   //(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)
   //
   //一通如下操作
   //union(4, 3); // 4->3
   //0123456789
   //-------------------------------------
   //0123356789
   //
   //union(3, 8); // 3->8
   //0123456789
   //-------------------------------------
   //0128356789
   //
   //union(6, 5); // 6->5
   //0123456789
   //-------------------------------------
   //0128355789
   //
   //union(9, 4); // 4->33->8 所以 9->8
   //0123456789
   //-------------------------------------
   //0128355788
   //
   //union(2, 1); // 2->1
   //0123456789
   //-------------------------------------
   //0118355788
   //
   //union(5, 0); // 5->0
   //0123456789
   //-------------------------------------
   //0118305788
   //
   //union(7, 2); // 2->1 所以 7->1
   //0123456789
   //-------------------------------------
   //0118305188
   //
   //union(6, 2); // 6->5 5->0,2->1 所以0->1
   //0123456789
   //-------------------------------------
   //1118305188
   複製程式碼

4. QuickUnion 的方式實現並查集中的 union 操作的時間複雜度是O(h)

   1. 這個 h 是當前 union 的這兩個元素它所在的樹相應的深度大小，
   2. 這個深度的大小在通常的情況下都比元素的個數 n 要小，
   3. 所以 union 的這個過程相對之前要快一些，
   4. 不過相應的代價就是 查詢的過程相應的時間複雜度依然是樹的深度大小，
   5. 所以就稍微犧牲了一些查詢時相應的效能，
   6. 不過由於在通常情況下這棵樹的高度是遠遠小於資料總量 n 的，
   7. 所以要讓合併和查詢這兩個操作都是樹的高度這個時間複雜度，
   8. 相應的在大多數運用中這個效能是可以接受的，
   9. 當然目前實現的並查集還是有很大的優化空間的。

5. 這個版本的並查集雖然是使用陣列來進行儲存的

   1. 但是它實際上是一種非常奇怪的樹，這種樹是由孩子指向父親的。

程式碼示例

1. MyUnionFindTwo

   // 自定義並查集 UnionFind 第二個版本 QuickUnion版
   // Union 操作變快了
   // 還可以更快的
   class MyUnionFindTwo {
   constructor(size) {
   // 儲存當前節點所指向的父節點
   this.forest = new Array(size);
   
   // 在初始的時候每一個節點都指向它自己
   // 也就是每一個節點都是獨立的一棵樹
   const len = this.forest.length;
   for (var i = 0; i < len; i++) this.forest[i] = i;
   }
   
   // 功能：將元素q和元素p這兩個資料以及他們所在的集合進行合併
   // 時間複雜度：O(h) h 為樹的高度
   unionElements(treePrimary, treeSecondary) {
   const primaryRoot = this.find(treePrimary);
   const secondarRoot = this.find(treeSecondary);
   
   if (primaryRoot === secondarRoot) return;
   
   // 無論哪棵樹往那棵樹上進行合併 都一樣，他們都是樹
   // 這裡是主樹節點上往次樹節點進行合併
   this.forest[primaryRoot] = this.forest[secondarRoot];
   }
   
   // 功能：查詢元素q和元素p這兩個資料是否在同一個集合中
   // 時間複雜度：O(h) h 為樹的高度
   isConnected(treeQ, treeP) {
   return this.find(treeQ) === this.find(treeP);
   }
   
   // 查詢元素所對應的集合編號
   find(id) {
   if (id < 0 || id >= this.ids.length)
   throw new Error('index is out of bound.');
   
   // 不斷的去查查詢當前節點的根節點
   // 根節點的索引是指向自己，如果根節點為 1 那麼對應的索引也為 1。
   while (id !== this.forest[id]) id = this.forest[id];
   
   return id;
   }
   
   // 功能：當前並查集一共考慮多少個元素
   getSize() {
   return this.ids.length;
   }
   }
   複製程式碼

並查集 Quick Union 基於 Size 的優化

1. 兩版並查集的比較
   1. 第二版的 QuickUnion 方式的並查集和
   2. 第一版 QuickFind 方式的並查集在思路上有非常大的不同，
   3. 第一版的並查集實際上就是使用陣列來模擬每個資料所屬的集合是誰，
   4. 第二版的並查集雖然也是使用陣列進行資料關係的儲存，
   5. 但整體思路上和第一版的並查集是截然不同的，
   6. 因為讓資料形成了一棵比較奇怪的樹結構，更準確的說是森林結構，
   7. 在這個森林中每一棵樹相應的節點之間的關係都是孩子指向父親的，
   8. 這樣一來可以通過任意的節點非常容易的查詢到這棵樹相應的根節點是誰，
   9. 那麼相應的就知道了對於每一個節點來說它所屬的集合編號是誰。
2. 兩個版本的並查集的效能

   O(1)
   O(n)
   O(h)
   O(h)
   

3. 在測試演算法效能時候

   O(h)
   O(h)
   O(n)
   

4. 優化第二個版本的並查集
   1. 這個優化空間主要在於，在進行 union 操作的時候，
   2. 就直接將 q 這個元素的根節點直接去指向了 p 這個元素的根節點，
   3. 但是沒有充分的考慮 q 和 p 這兩個元素它所在的那兩棵樹的特點是怎樣的，
   4. 如果不對要合併的那兩個元素所在的樹的形狀不去做判斷，
   5. 很多時候這個合併的過程會不斷的增加樹的高度，
   6. 甚至在一些極端的情況下得到的這棵樹是一條連結串列的樣子。
5. 簡單的解決方案：考慮 size

   O(h)
   

程式碼示例

1. (class: MyUnionFindOne, class: MyUnionFindTwo, class: MyUnionFindThree, class: PerformanceTest, class: Main)

2. MyUnionFindOne

   // 自定義並查集 UnionFind 第一個版本 QuickFind版
   // isConnected 操作很快
   class MyUnionFindOne {
   constructor(size) {
   // 儲存資料所對應的集合的編號
   this.ids = new Array(size);
   
   // 模擬存入資料
   const len = this.ids.length;
   for (var i = 0; i < len; i++) this.ids[i] = i;
   }
   
   // 功能：將元素q和元素p這兩個資料以及他們所在的集合進行合併
   // 時間複雜度：O(n)
   unionElements(q, p) {
   const qId = this.find(q);
   const pId = this.find(p);
   
   if (qId === pId) return;
   
   for (var i = 0; i < this.ids.length; i++)
   if (pId === this.ids[i]) this.ids[i] = qId;
   }
   
   // 功能：查詢元素q和元素p這兩個資料是否在同一個集合中
   // 時間複雜度：O(1)
   isConnected(q, p) {
   return this.ids[q] === this.ids[p];
   }
   
   // 查詢元素所對應的集合編號
   find(index) {
   if (index < 0 || index >= this.ids.length)
   throw new Error('index is out of bound.');
   return this.ids[index];
   }
   
   // 功能：當前並查集一共考慮多少個元素
   getSize() {
   return this.ids.length;
   }
   }
   複製程式碼

3. MyUnionFindTwo

   // 自定義並查集 UnionFind 第二個版本 QuickUnion版
   // Union 操作變快了
   // 還可以更快的
   class MyUnionFindTwo {
   constructor(size) {
   // 儲存當前節點所指向的父節點
   this.forest = new Array(size);
   
   // 在初始的時候每一個節點都指向它自己
   // 也就是每一個節點都是獨立的一棵樹
   const len = this.forest.length;
   for (var i = 0; i < len; i++) this.forest[i] = i;
   }
   
   // 功能：將元素q和元素p這兩個資料以及他們所在的集合進行合併
   // 時間複雜度：O(h) h 為樹的高度
   unionElements(treePrimary, treeSecondary) {
   const primaryRoot = this.find(treePrimary);
   const secondarRoot = this.find(treeSecondary);
   
   if (primaryRoot === secondarRoot) return;
   
   // 無論哪棵樹往那棵樹上進行合併 都一樣，他們都是樹
   // 這裡是主樹節點上往次樹節點進行合併
   this.forest[primaryRoot] = this.forest[secondarRoot];
   }
   
   // 功能：查詢元素q和元素p這兩個資料是否在同一個集合中
   // 時間複雜度：O(h) h 為樹的高度
   isConnected(treeQ, treeP) {
   return this.find(treeQ) === this.find(treeP);
   }
   
   // 查詢元素所對應的集合編號
   find(id) {
   if (id < 0 || id >= this.forest.length)
   throw new Error('index is out of bound.');
   
   // 不斷的去查查詢當前節點的根節點
   // 根節點的索引是指向自己，如果根節點為 1 那麼對應的索引也為 1。
   while (id !== this.forest[id]) id = this.forest[id];
   
   return id;
   }
   
   // 功能：當前並查集一共考慮多少個元素
   getSize() {
   return this.forest.length;
   }
   }
   複製程式碼

4. MyUnionFindThree

   // 自定義並查集 UnionFind 第三個版本 QuickUnion優化版
   // Union 操作變快了
   // 還可以更快的
   // 解決方案：考慮size 也就是某一棵樹從根節點開始一共有多少個節點
   // 原理：節點少的向節點多的樹進行融合
   // 還可以更快的
   class MyUnionFindThree {
   constructor(size) {
   // 儲存當前節點所指向的父節點
   this.forest = new Array(size);
   // 以以某個節點為根的所有子節點的個數
   this.branch = new Array(size);
   
   // 在初始的時候每一個節點都指向它自己
   // 也就是每一個節點都是獨立的一棵樹
   const len = this.forest.length;
   for (var i = 0; i < len; i++) {
   this.forest[i] = i;
   this.branch[i] = 1; // 預設節點個數為1
   }
   }
   
   // 功能：將元素q和元素p這兩個資料以及他們所在的集合進行合併
   // 時間複雜度：O(h) h 為樹的高度
   unionElements(treePrimary, treeSecondary) {
   const primaryRoot = this.find(treePrimary);
   const secondarRoot = this.find(treeSecondary);
   
   if (primaryRoot === secondarRoot) return;
   
   // 節點少的 樹 往 節點多的樹 進行合併，在一定程度上減少最終樹的高度
   if (this.branch[primaryRoot] < this.branch[secondarRoot]) {
   // 主樹節點上往次樹節點進行合併
   this.forest[primaryRoot] = this.forest[secondarRoot];
   // 次樹的節點個數 += 主樹的節點個數
   this.branch[secondarRoot] += this.branch[primaryRoot];
   } else {
   // branch[primaryRoot] >= branch[secondarRoot]
   // 次樹節點上往主樹節點進行合併
   this.forest[secondarRoot] = this.forest[primaryRoot];
   // 主樹的節點個數 += 次樹的節點個數
   this.branch[primaryRoot] += this.branch[secondarRoot];
   }
   }
   
   // 功能：查詢元素q和元素p這兩個資料是否在同一個集合中
   // 時間複雜度：O(h) h 為樹的高度
   isConnected(treeQ, treeP) {
   return this.find(treeQ) === this.find(treeP);
   }
   
   // 查詢元素所對應的集合編號
   find(id) {
   if (id < 0 || id >= this.forest.length)
   throw new Error('index is out of bound.');
   
   // 不斷的去查查詢當前節點的根節點
   // 根節點的索引是指向自己，如果根節點為 1 那麼對應的索引也為 1。
   while (id !== this.forest[id]) id = this.forest[id];
   
   return id;
   }
   
   // 功能：當前並查集一共考慮多少個元素
   getSize() {
   return this.forest.length;
   }
   }
   複製程式碼

5. PerformanceTest

   // 效能測試
   class PerformanceTest {
   constructor() {}
   
   // 對比佇列
   testQueue(queue, openCount) {
   let startTime = Date.now();
   
   let random = Math.random;
   for (var i = 0; i < openCount; i++) {
   queue.enqueue(random() * openCount);
   }
   
   while (!queue.isEmpty()) {
   queue.dequeue();
   }
   
   let endTime = Date.now();
   
   return this.calcTime(endTime - startTime);
   }
   
   // 對比棧
   testStack(stack, openCount) {
   let startTime = Date.now();
   
   let random = Math.random;
   for (var i = 0; i < openCount; i++) {
   stack.push(random() * openCount);
   }
   
   while (!stack.isEmpty()) {
   stack.pop();
   }
   
   let endTime = Date.now();
   
   return this.calcTime(endTime - startTime);
   }
   
   // 對比集合
   testSet(set, openCount) {
   let startTime = Date.now();
   
   let random = Math.random;
   let arr = [];
   let temp = null;
   
   // 第一遍測試
   for (var i = 0; i < openCount; i++) {
   temp = random();
   // 新增重複元素，從而測試集合去重的能力
   set.add(temp * openCount);
   set.add(temp * openCount);
   
   arr.push(temp * openCount);
   }
   
   for (var i = 0; i < openCount; i++) {
   set.remove(arr[i]);
   }
   
   // 第二遍測試
   for (var i = 0; i < openCount; i++) {
   set.add(arr[i]);
   set.add(arr[i]);
   }
   
   while (!set.isEmpty()) {
   set.remove(arr[set.getSize() - 1]);
   }
   
   let endTime = Date.now();
   
   // 求出兩次測試的平均時間
   let avgTime = Math.ceil((endTime - startTime) / 2);
   
   return this.calcTime(avgTime);
   }
   
   // 對比對映
   testMap(map, openCount) {
   let startTime = Date.now();
   
   let array = new MyArray();
   let random = Math.random;
   let temp = null;
   let result = null;
   for (var i = 0; i < openCount; i++) {
   temp = random();
   result = openCount * temp;
   array.add(result);
   array.add(result);
   array.add(result);
   array.add(result);
   }
   
   for (var i = 0; i < array.getSize(); i++) {
   result = array.get(i);
   if (map.contains(result)) map.add(result, map.get(result) + 1);
   else map.add(result, 1);
   }
   
   for (var i = 0; i < array.getSize(); i++) {
   result = array.get(i);
   map.remove(result);
   }
   
   let endTime = Date.now();
   
   return this.calcTime(endTime - startTime);
   }
   
   // 對比堆 主要對比 使用heapify 與 不使用heapify時的效能
   testHeap(heap, array, isHeapify) {
   const startTime = Date.now();
   
   // 是否支援 heapify
   if (isHeapify) heap.heapify(array);
   else {
   for (const element of array) heap.add(element);
   }
   
   console.log('heap size:' + heap.size() + '\r\n');
   document.body.innerHTML += 'heap size:' + heap.size() + '<br /><br />';
   
   // 使用陣列取值
   let arr = new Array(heap.size());
   for (let i = 0; i < arr.length; i++) arr[i] = heap.extractMax();
   
   console.log(
   'Array size:' + arr.length + '，heap size:' + heap.size() + '\r\n'
   );
   document.body.innerHTML +=
   'Array size:' +
   arr.length +
   '，heap size:' +
   heap.size() +
   '<br /><br />';
   
   // 檢驗一下是否符合要求
   for (let i = 1; i < arr.length; i++)
   if (arr[i - 1] < arr[i]) throw new Error('error.');
   
   console.log('test heap completed.' + '\r\n');
   document.body.innerHTML += 'test heap completed.' + '<br /><br />';
   
   const endTime = Date.now();
   return this.calcTime(endTime - startTime);
   }
   
   // 對比並查集
   testUnionFind(unionFind, openCount, primaryArray, secondaryArray) {
   const size = unionFind.getSize();
   const random = Math.random;
   
   return this.testCustomFn(function() {
   // 合併操作
   for (var i = 0; i < openCount; i++) {
   let primaryId = primaryArray[i];
   let secondaryId = secondaryArray[i];
   
   unionFind.unionElements(primaryId, secondaryId);
   }
   
   // 查詢連線操作
   for (var i = 0; i < openCount; i++) {
   let primaryRandomId = Math.floor(random() * size);
   let secondaryRandomId = Math.floor(random() * size);
   
   unionFind.unionElements(primaryRandomId, secondaryRandomId);
   }
   });
   }
   
   // 計算執行的時間，轉換為 天-小時-分鐘-秒-毫秒
   calcTime(result) {
   //獲取距離的天數
   var day = Math.floor(result / (24 * 60 * 60 * 1000));
   
   //獲取距離的小時數
   var hours = Math.floor((result / (60 * 60 * 1000)) % 24);
   
   //獲取距離的分鐘數
   var minutes = Math.floor((result / (60 * 1000)) % 60);
   
   //獲取距離的秒數
   var seconds = Math.floor((result / 1000) % 60);
   
   //獲取距離的毫秒數
   var milliSeconds = Math.floor(result % 1000);
   
   // 計算時間
   day = day < 10 ? '0' + day : day;
   hours = hours < 10 ? '0' + hours : hours;
   minutes = minutes < 10 ? '0' + minutes : minutes;
   seconds = seconds < 10 ? '0' + seconds : seconds;
   milliSeconds =
   milliSeconds < 100
   ? milliSeconds < 10
   ? '00' + milliSeconds
   : '0' + milliSeconds
   : milliSeconds;
   
   // 輸出耗時字串
   result =
   day +
   '天' +
   hours +
   '小時' +
   minutes +
   '分' +
   seconds +
   '秒' +
   milliSeconds +
   '毫秒' +
   '<<<<============>>>>總毫秒數：' +
   result;
   
   return result;
   }
   
   // 自定義對比
   testCustomFn(fn) {
   let startTime = Date.now();
   
   fn();
   
   let endTime = Date.now();
   
   return this.calcTime(endTime - startTime);
   }
   }
   複製程式碼

6. Main

   // main 函式
   class Main {
   constructor() {
   this.alterLine('UnionFind Comparison Area');
   // 十萬級別
   const size = 100000; // 並查集維護節點數
   const openCount = 100000; // 運算元
   
   // 生成同一份測試資料的輔助程式碼
   const random = Math.random;
   const primaryArray = new Array(openCount);
   const secondaryArray = new Array(openCount);
   
   // 生成同一份測試資料
   for (var i = 0; i < openCount; i++) {
   primaryArray[i] = Math.floor(random() * size);
   secondaryArray[i] = Math.floor(random() * size);
   }
   
   // 開始測試
   const myUnionFindOne = new MyUnionFindOne(size);
   const myUnionFindTwo = new MyUnionFindTwo(size);
   const myUnionFindThree = new MyUnionFindThree(size);
   const performanceTest = new PerformanceTest();
   
   // 測試後獲取測試資訊
   const myUnionFindOneInfo = performanceTest.testUnionFind(
   myUnionFindOne,
   openCount,
   primaryArray,
   secondaryArray
   );
   const myUnionFindTwoInfo = performanceTest.testUnionFind(
   myUnionFindTwo,
   openCount,
   primaryArray,
   secondaryArray
   );
   const myUnionFindThreeInfo = performanceTest.testUnionFind(
   myUnionFindThree,
   openCount,
   primaryArray,
   secondaryArray
   );
   
   // 總毫秒數：24143
   console.log(
   'MyUnionFindOne time：' + myUnionFindOneInfo,
   myUnionFindOne
   );
   this.show('MyUnionFindOne time：' + myUnionFindOneInfo);
   // 總毫秒數：32050
   console.log(
   'MyUnionFindTwo time：' + myUnionFindTwoInfo,
   myUnionFindTwo
   );
   this.show('MyUnionFindTwo time：' + myUnionFindTwoInfo);
   // 總毫秒數：69
   console.log(
   'MyUnionFindThree time：' + myUnionFindThreeInfo,
   myUnionFindThree
   );
   this.show('MyUnionFindThree time：' + myUnionFindThreeInfo);
   }
   
   // 將內容顯示在頁面上
   show(content) {
   document.body.innerHTML += `${content}<br /><br />`;
   }
   
   // 展示分割線
   alterLine(title) {
   let line = `--------------------${title}----------------------`;
   console.log(line);
   document.body.innerHTML += `${line}<br /><br />`;
   }
   }
   
   // 頁面載入完畢
   window.onload = function() {
   // 執行主函式
   new Main();
   };
   複製程式碼

並查集 Quick Union 基於 Rank 的優化

1. 這個 rank 就是指樹的高度或樹的深度
   1. 之所以不叫做 height 和 depth，
   2. 是因為進行路徑壓縮的時候並不會維護這個 rank 了，
   3. rank 只在 union 中進行維護，
   4. 這個 rank 準確的來說只是一個粗略的排名或者序而已，
   5. 並不是很準確的儲存了樹的高度或深度。
2. rank 的優化是基於 size 優化的基礎上進行的

   rank[i]
   

3. rank 的優化效能其實和 size 優化的效能差不了多少
   1. 但是當資料量達到千萬這個程度的時候，
   2. 就會有一點差距了，差距也不是有點大，就一兩秒左右。
   3. 所以還是有優化空間的。