------------------siwuxie095
基于 rank 的优化
基于
size 的优化，在大多数情况下，都能让生成的树的层数更少，
从而使得查询的时间更短，但仍有少数情况不是这样，如下：
现在要将 4 和 2 这两个元素并在一起，4 对应的根是 8，2 对应的根是 7，
其中： 8 所在的集合一共有 3 个元素，而 7 所在的集合一共有 6 个元素，
显然，基于
size 的优化，经过 Union 操作后，就应该是下面的样子：
注意：原来两棵树的层数分别为 2 和 3，合并后层数却变成了 4，
但假如换一个方向，将 7 的指向父亲的指针指向 8 的话，得到的
新树的层数为 3，比刚才的做法层数要少，如下：
即
依靠集合的
size 来判断由谁指向谁，并不是完全准确的，更准确
的方式是：根据两个集合所表示的树的层数来判断由谁指向谁
在并查集中，通常使用一个叫做
rank 的数组来表示层数。设立一个
rank 数组，rank[i] 表示根节点为 i 的树的高度
程序：基于
rank 的优化
UnionFind.h：
#ifndef UNIONFIND_H #define UNIONFIND_H #include <cassert> using namespace std; //并查集：Quick Union + rank namespace UF { class UnionFind { private: int* parent; int* rank; // rank[i]表示以i为根的集合所表示的树的层数 int count; public: UnionFind(int count) { this->count = count; parent = new rank = new //在初始情况下，并查集里的元素，两两之间互不连接 for (int i = 0; i < count; i++) { parent[i] = i; rank[i] = 1; } } ~UnionFind() { delete []parent; delete []rank; } int find(int p) { assert(p >= 0 && p < count); //不断追溯，直到p等于parent[p]，即 p 为根节点，返回 p //（返回的是根节点） while (p != parent[p]) { p = parent[p]; } return p; } bool isConnected(int p, int q) { return find(p) == find(q); } void unionElements(int p, int q) { int pRoot = find(p); int qRoot = find(q); if (pRoot == qRoot) { return; } //rank小的那棵树的根节点指向rank大的那棵树的根节点 if (rank[pRoot] < rank[qRoot]) { parent[pRoot] = qRoot; } else if (rank[qRoot] < rank[pRoot]) { parent[qRoot] = pRoot; } // rank[pRoot] == rank[qRoot] else { //可互换 parent[pRoot] = qRoot; rank[qRoot] += 1; } } }; } #endif |
UnionFindTestHelper.h：
#ifndef UNIONFINDTESTHELPER_H #define UNIONFINDTESTHELPER_H #include #include <iostream> #include <ctime> using namespace std; namespace UnionFindTestHelper { void testUF(int n) { //设置随机种子 srand(time(NULL)); UF::UnionFind uf = UF::UnionFind(n); time_t startTime = clock(); //先进行n次的并，即 Union 操作 for (int i = 0; i < n; i++) { int a = rand() % n; int b = rand() % n; uf.unionElements(a, b); } //再进行n次的查，即 Find 操作 for (int i = 0; i < n; i++) { int a = rand() % n; int b = rand() % n; uf.isConnected(a, b); } time_t endTime = clock(); //打印2*n个操作耗费的时间 cout << "UF, " << 2 * n << " ops, " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl; } } #endif |
main.cpp：
#include #include <iostream> using namespace std; int main() { //规模是一百万 int n = 1000000; UnionFindTestHelper::testUF(n); system("pause"); return } |
运行一览：
【made by siwuxie095】