----------------------siwuxie095
基于 size 的优化
在 union( p , q ) 的时候，因为总是将第一个元素的根节点指向第二个元素
的根节点，就有可能让整棵树变的很高，导致 find( p ) 更耗时
解决方案：不应该固定的将一个元素的根节点指向另外一个元素的根节点，
而应该在做具体的指向操作之前，进行一下判断：判断两个元素所在集合
的元素总数谁大谁小
具体实现：存储每一个集合中元素的个数，在进行 Union 操作时，永远将
元素少的那组集合的根节点指向元素多的那组集合的根节点
这样一来，将会有更高概率形成一棵层数比较低的树
程序：基于 size 的优化
UnionFind.h：
#ifndef UNIONFIND_H #define UNIONFIND_H
#include <cassert> using namespace std;
//并查集：Quick Union + size namespace UF {
class UnionFind {
private: int* parent; int* sz; // sz[i]表示以i为根的集合中元素个数 int count;
public: UnionFind(int count) { this->count = count; parent = new int[count]; sz = new int[count]; //在初始情况下，并查集里的元素，两两之间互不连接 for (int i = 0; i < count; i++) { parent[i] = i; sz[i] = 1; } }
~UnionFind() { delete []parent; delete []sz; }
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; }
//size小的那棵树的根节点指向size大的那棵树的根节点 if (sz[pRoot] < sz[qRoot]) { parent[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; } else { parent[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } } }; }
#endif |
UnionFindTestHelper.h：
#ifndef UNIONFINDTESTHELPER_H #define UNIONFINDTESTHELPER_H
#include "UnionFind.h" #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 "UnionFindTestHelper.h" #include <iostream> using namespace std;
int main() { //规模是一百万 int n = 1000000;
UnionFindTestHelper::testUF(n);
system("pause"); return 0; } |
运行一览：
【made by siwuxie095】