并查集系列之「基于size的优化」

并查集基于size的优化

一、介绍及逻辑

  1. 介绍
    在上一小节我们使用指针的方法将每一个元素都看作是一个节点,并且是节点指向另一个节点(包括自己),在这一小节中我们将在此基础上进行优化。
    先来介绍一下什么是”size”
    size : size[i] 是指用来记录以i为根节点的树所包含的节点个数,本质是一个数组

  2. 逻辑
    先来看看下面的图片:
    现在需要将4,2连接起来,该怎么连?

并查集系列之「基于sz的优化」

方法一:如下图

并查集系列之「基于sz的优化」

方法二:如下图

并查集系列之「基于sz的优化」

很容易看出方法二更优,树的高度越高,对计算机的消耗也会越大,所以很明显方法二是有3层,而方法一有4层(一旦有大量的数据时,性能差别就会明显); 所以我们使用size数组,就是在维护方法二。

二、代码实现

#include<cassert>

using namespace std;
namespace UF3 {
 class UnionFind2 {
   private:
  // 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树
 // parent[i]表示第i个元素所指向的父节点 
    int *parent;
    int *size;  //size用来记录节点的个数
    int count; //数据个数

    public:
        UnionFind2(int count) {
            parent = new int[count];
            size = new int[count];
            this->count = count;
            //初始化
            for (int i = 0; i < count; i++) {
                parent[i] = i;
                size[i] = 1;
             }
       }
         //析构函数
        ~UnionFind2() {
            delete parent;
            delete size;
  }

        // 查找过程, 查找元素p所对应的集合编号
 // O(h)复杂度, h为树的高度 
         int find(int p) {
            assert(p >= 0 && p <= count);
           // 不断去查询自己的父亲节点, 直到到达根节点
           // 根节点的特点: parent[p] == p  
            while (p != parent[p])
                  p = parent[p];
            return p;
  }

        // 查看元素p和元素q是否所属一个集合
        // O(h)复杂度, h为树的高度 
        bool isConnected(int p, int q) {
            return find(p) == find(q);
  }

下面是size的核心:

         // 合并元素p和元素q所属的集合
         // O(h)复杂度, h为树的高度  
        void unionElments(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);

            if (pRoot == qRoot)
                return;
             // 根据两个元素所在树的元素个数不同判断合并方向
             // 将元素个数少的集合合并到元素个数多的集合上
            if(size[pRoot] < size[qRoot]) {
                parent[pRoot] = qRoot;
                size[qRoot] = +size[pRoot];
             }
            else {   //size[pRoot] >= size[qRoot]
                parent[qRoot] = pRoot;
                size[pRoot] = +size[qRoot];
             }
        }
    };
}


本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!