Data Structure_堆_二叉树_并查集

  1. 云栖社区>
  2. 博客>
  3. 正文

Data Structure_堆_二叉树_并查集

绿箭侠2017 2018-10-19 22:53:00 浏览692
展开阅读全文

堆这种数据结构的应用很广泛,比较常用的就是优先队列。普通的队列就是先进先出,后进后出。优先队列就不太一样,出队顺序和入队顺序没有关系,只和这个队列的优先级相关,比如去医院看病,你来的早不一定是先看你,因为病情严重的病人可能需要优先接受治疗,这就和时间顺序没有必然联系。优先队列最频繁的应用就是操作系统,操作系统的执行是划分成一个一个的时间片的,每一次在时间片里面的执行的任务是选择优先级最高的队列,如果一开始这个优先级是固定的可能就很好选,但是在操作系统里面这个优先级是动态变化的,随着执行变化的,所以每一次如果要变化,就可以使用优先队列来维护,每一次进或者出都动态着在优先队列里面变化。在游戏中也有使用到,比如攻击对象,也是一个优先队列。所以优先队列比较适合处理一些动态变化的问题,当然对于静态的问题也可以求解,比如求解1000个数字的前100位出来,最简单的方法就是排序了,,但是这样多此一举,直接构造一个优先队列,然后出的时候出一百次最大的元素即可。这个时候算法的复杂度就是NlogN,如果使用优先队列可以降到NlogM的级别。

入队 出队
普通数组 O(1) O(n)
顺序数组 O(n) O(1)
O(lgn) O(lgn)

现在就要用堆来实现一个优先队列堆一般都是树形结构:

img_3eee9eaec3f34b1790431debfac97c06.png
二叉堆就和二叉树有点相像,没一个节点都有两个子节点,而且任何一个字节点都不会大于它的父节点,当然这样构造出来的就是一个最大堆了,也可以每一个子节点不小于它的父节点,这样就是最小堆了。而且,这个二叉堆一定是一个完全二叉树,非最后一层的节点一定要是满的,最后一层的节点一定要集中在左边:
img_35e46fb3c5a0192d8a6683eb9ddb7bcb.png
这个性质,非常好,所以可以用给一个数组来表示堆。另外,层数越高并不意味着数值就越大或者越小,可以从右边的图看的出来。
img_05230dcfc66c3621c3f3aba1a8d3373a.png
可以看的出来,每一个节点子节点都是父节点的两倍。对于一个子节点,想要找到它的父类就直接/2即可,这里用的是四舍五入的除法,所以直接就向下取整了。父节点找子节点,左孩子2i,右孩子2i+1即可。首先是建立一个堆,这个还是蛮简单的:

template<typename item>
class MaxHeap {
private:
    item *data;
    int count = 0;
public:
    MaxHeap(int capacity){
        data = new item[capacity + 1];
        count = 0;
    }
    ~MaxHeap(){
        delete[] data;
    }
    int size(){
        return count;
    }
    bool isEmpty(){
        return count == 0;
    }
};

对于插入一个元素其实也很简单,直接放到最后然后再一步一步的浮上来。新加入的那个元素和他的父亲对比,如果是大于它父亲那么就交换,只到是不大于或者是到了1。因为如果是小于父亲节点那就本身是正确的,如果不终止,再往下比那就是比较其他的元素了,但是其他元素本来就是正确的,所以不需要比较直接结束好了。

    void shiftUp(int index) {
        while (index > 1 && data[index / 2] < data[index]) {
            swap(data[index / 2], data[index]);
            index /= 2;
        }
    }
    void insert(item number) {
        assert(count + 1 <= capacity);
        data[count + 1] = number;
        count++;
        shiftUp(count);
    }

这样就完成了插入。对于弹出最大的元素就有点边界问题要讨论了。这是一个完全二叉树,所以只有左节点没有右节点,所以首先先要判断是不是有做孩子,也就是越界的问题了,如果没有就继续判断有没有右孩子,有的话就左右孩子比较咯,哪个大就拿哪个出来,在把最大的拿出来和原节点比较即可。这里就需要一个额外的变量了。

    void shiftDown(int index) {
        while (2 * index <= count) {
            int change = 2 * index;
            if (change + 1 < count && data[change + 1] > data[change]) {
                change++;
            }
            if (data[change] <= data[index]) {
                break;
            }
            swap(data[change], data[index]);
            index = change;
        }
    }
    item pop() {
        assert(count > 0);
        item target = data[1];
        swap(data[1], data[count]);
        count--;
        shiftDown(1);
        return target;
    }

这样就完成了弹出,弹出的就是最大的数字。事实上这样是可以直接做排序操作的。
现在使用的堆数据结构,是通过不断的交换元素来达到符合堆这个数据结构的目的,但是如果堆里面的元素不是数字,而是字符串或者是很长很长的其他复杂的数据结构,那么交换起来效率就很低,而且这样的话索引起来也有难度。为了解决这些问题,于是就引入了索引堆来解决:

img_36a9b95bd2ecfcc244290c5b2f8f06a9.png

每一个元素加上一个索引值
img_a3051dec406188b952c2a3dce9b427d4.png
交换的时候就只是需要交换索引值即可,第一个元素的索引是10,那么就是对应着索引下标的62。对于查找,也很简单,直接索引下标即可。修改起来也很简单,大致是和之前一样,只不过是修改的时候就是修改索引即可。
首先是对于索引堆的创建,我们不仅仅是要一个存储数据的数组,还要一个存储索引的数组,因为最后改变的是使用索引,索引对应下的数组是不变的。:

template<typename item>
class IndexHeap {
private:
    item *indexes;
    item *data;
    int count;
    int capacity;

shiftDown和shiftUp操作其实就是变一下,把交换的对象换成索引即可:

    void shiftUp(int k) {
        while (k > 1 && data[indexes[k / 2]] < data[indexes[k]]) {
            swap(indexes[k / 2], indexes[k]);
            k /= 2;
        }
    }

    void shitDown(int k) {
        while (2 * k <= count) {
            int change = 2 * k;
            if (change + 1 <= count && data[indexes[change]] < data[indexes[change + 1]]) {
                change++;
            }
            if (data[indexes[change]] <= data[indexes[k]]) {
                break;
            }
            swap(indexes[change], indexes[k]);
            k = change;
        }
    }

弹出和插入都是一样的:

    void insert(int i, item itemNumber) {
        assert(count + 1 <= capacity);
        assert(i + 1 >= 1 && i + 1 < capacity);
        i++;
        data[i] = itemNumber;
        indexes[++count] = i;
        shiftUp(count);
    }

    item extractMax(){
        item num = data[indexes[1]];
        swap(indexes[1], indexes[count]);
        count -- ;
        shitDown(1);
        return num;
    }

主要的变化就是对于改变对应索引下的一个元素。改变了之后,我们要知道这个元素的索引是在这个堆的第几个位置才可以进行shift操作,之后还要进行shifDown和shiftUp操作,因为不知道它是可以上浮还是下沉。

    void change(int i, item itemNumber){
        i += 1;
        data[i] = itemNumber;
        for (int j = 1; j <= count; ++j) {
            if (indexes[j] == i){
                shiftUp(j);
                shitDown(j);
                return;
            }
        }
    }

但是这个种改变方法最差的情况下是O(nlogn),最后还可以使用一种反向查找的方法进行改进,可以将复杂度提升到O(1)。使用一个reverse数组存储当前索引所在的位置,只有在修改了元素之后就可以直接用O(1)的复杂度从reverse中取出来了。所以有reverse[index[i]] = i,reverse[index]就可以找到当前的元素的位置了。修改代码很简单,reverse和index是绑定在一起的,所以只要index变的地方reverse也要变的。

template<typename Item>
class IndexMinHeap{

private:
    Item *data;
    int *indexes;
    int *reverse;

    int count;
    int capacity;

    void shiftUp( int k ){

        while( k > 1 && data[indexes[k/2]] > data[indexes[k]] ){
            swap( indexes[k/2] , indexes[k] );
            reverse[indexes[k/2]] = k/2;
            reverse[indexes[k]] = k;
            k /= 2;
        }
    }

    void shiftDown( int k ){

        while( 2*k <= count ){
            int j = 2*k;
            if( j + 1 <= count && data[indexes[j]] > data[indexes[j+1]] )
                j += 1;

            if( data[indexes[k]] <= data[indexes[j]] )
                break;

            swap( indexes[k] , indexes[j] );
            reverse[indexes[k]] = k;
            reverse[indexes[j]] = j;
            k = j;
        }
    }

public:
    IndexMinHeap(int capacity){

        data = new Item[capacity+1];
        indexes = new int[capacity+1];
        reverse = new int[capacity+1];

        for( int i = 0 ; i <= capacity ; i ++ )
            reverse[i] = 0;

        count = 0;
        this->capacity = capacity;
    }

    ~IndexMinHeap(){
        delete[] data;
        delete[] indexes;
        delete[] reverse;
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }

    void insert(int index, Item item){
        assert( count + 1 <= capacity );
        assert( index + 1 >= 1 && index + 1 <= capacity );

        index += 1;
        data[index] = item;
        indexes[count+1] = index;
        reverse[index] = count+1;
        count++;
        shiftUp(count);
    }

    Item extractMin(){
        assert( count > 0 );

        Item ret = data[indexes[1]];
        swap( indexes[1] , indexes[count] );
        reverse[indexes[count]] = 0;
        reverse[indexes[1]] = 1;
        count--;
        shiftDown(1);
        return ret;
    }

    int extractMinIndex(){
        assert( count > 0 );

        int ret = indexes[1] - 1;
        swap( indexes[1] , indexes[count] );
        reverse[indexes[count]] = 0;
        reverse[indexes[1]] = 1;
        count--;
        shiftDown(1);
        return ret;
    }

    Item getMin(){
        assert( count > 0 );
        return data[indexes[1]];
    }

    int getMinIndex(){
        assert( count > 0 );
        return indexes[1]-1;
    }

    bool contain( int index ){
        return reverse[index+1] != 0;
    }

    Item getItem( int index ){
        assert( contain(index) );
        return data[index+1];
    }

    void change( int index , Item newItem ){

        assert( contain(index) );
        index += 1;
        data[index] = newItem;

        shiftUp( reverse[index] );
        shiftDown( reverse[index] );
    }

};

堆可以解决的一些问题,首先,就是使用堆来实现优先队列,实现一些选择优先级最高的任务执行。可以作为一些低级工具来实现一些高级数据结构。

Tree

二叉树

二叉树比较常用的地方就是查找了,其实就是类似于二分查找法,把数据分成两份,使用logn这样的复杂度来进行查找搜索,但是这样就要求这个数组是有序的。比较常用的实现就是查找表的实现。如果使用顺序数组进行查找,使用的复杂度是logn,相对应的插入元素也是要o(n),因为它要遍历所有的元素找到相对应的位置然后插入。但是二分搜索树就更好一些,插入删除查找都是O(logn)的复杂度。所以,二分搜索树不仅可以查找数据,还可以高效的插入删除等等,效率很高,适合动态维护数据。而且这种方便的数据结构也可以很好的回答数据关系之间的问题。
二分搜索树首先是一颗二叉树:

img_53ae1e0353239e44b6cd90740681dca7.png
每个节点的建值大于左孩子小于右孩子,而以左右孩子为根的子树仍然是二分搜索树。对于堆来说一定是要完全二叉树,但是对于一个二分搜索树来说,是不一定的,所以二叉树就不能用数组来存储了。实现二叉树的结构其实很简单,按照查找表来实现,要有一个建和一个值。

template<typename Key, typename Value>
class BST{
private:
    struct Node{
        Key key;
        Value value;
        Node *left;
        Node *right;
        Node(Key key, Value value){
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }
    };
    Node *root;
    int count;
public:
    BST(){
        root = NULL;
        count = 0;
    }
    ~BST(){
        //TODO
    }
    int size(){
        return count;
    }
    bool isEmpty(){
        return count == 0;
    }
};

对于插入其实也很简单。首先和当前根节点比较,如果小于就往左边递归,大于就往右边递归,当当前节点是NULL的时候就到达了递归终点,这个时候已经到头了,new一个新的节点返回当前节点即可。

    void insert(Key key, Value value){
        root = insert(root, key, value);
    }

private:
    Node *insert(Node *node, Key key, Value value){
        if (node == NULL){
            count ++;
            return new Node(key, value);
        }
        if (node->key == key){
            node->value = value;
        } else if(key < node->key){
            node->left = insert(node->left, key, value);
        } else{
            node->right = insert(node->right, key, value);
        }
        return node;
    }

二叉树的包含,查找其实都很类似,都是小于往左边找,大于往右边找,只是返回值不一样,操作很常规,比较复杂的是删除操作,要旋转之类的。

    Value *search(Node *node, Key key){
        if (NULL == node){
            return NULL;
        } else if(node->key == key){
            return &(node->value);
        } else if(key < node->key){
            return search(node->left, key);
        } else{
            return search(node->right, key);
        }
    }

    bool contain(Node *node, Key key){
        if (NULL == node){
            return false;
        }
        if (node->key == key){
            return true;
        } else if(key < node->key){
            return contain(node->left, key);
        } else{
            return contain(node->right, key);
        }
    }
};

以上方法都是放在了私有方法里面的,要调用只需要在public里面加上调用即可:

    Value *search(Key key){
        return search(root, key);
    }

    bool contain(Key key){
        return contain(root, key);
    }

对于search的返回值,其实见仁见智,返回node,固定的一个值都可以。但是如果返回的是一个node,那么调用的时候就需要用户知道程序的结构,比如这道直观node节点是啥才能拿出来,这样封装性就不好了;如果返回的是一个值,那么如果为空的时候就回不来了,所以把它的指针作为返回值。
二叉树的遍历方式有三种,前序遍历,中序遍历和后续遍历。前序遍历先访问当前节点,再访问左右节点;中序遍历先访问左节点,再访问自身,最后右节点;后序遍历先访问左右子树最后才访问自身节点。

img_9fe26cade3cc5dfd7734d8355c26e9f5.png
每一个节点都会存在左右子树,用三个点来表示访问时输出的顺序。
img_b7dfe7e9d2892977307041bd95f67204.png

如果是前序遍历,那么输出的位置就是第一个园点的位置。中序遍历也是一样:
img_25c9473cff26bd47b3fd73f0eeb52895.png
中序遍历就是在遍历到中间那个点的时候就输出。后序遍历自然就是最后一个位置输出:
img_1911caaa6435ebbf4da26461cfa44d26.png
后序遍历有一个很好的应用,就是释放内存的时候可以使用后序遍历的操作。递归实现二叉树的遍历其实很简单,就是调换几个位置就好了,结合上面的图理解一下就好。

    void preOrder(Node *node){
        if (node != NULL){
            cout << node->value;
            preOrder(node->left);
            preOrder(node->right);
        }
    }

    void inOrder(Node *node){
        if (node != NULL){
            inOrder(node->left);
            cout << node->value;
            inOrder(node->right);
        }
    }

    void postOrder(Node * node){
        if (node != NULL){
            postOrder(node->left);
            postOrder(node->right);
            cout << node->value;
        }
    }

没有什么难度的。注意到后序遍历是左右才到中间,所以我们可以使用这种方法来对对整棵树进行释放。

    void destory(Node *node){
        if (node != NULL){
            destory(node->left);
            destory(node->right);
            delete node;
            count --;
        }
    }

之前我们遍历二叉树都是往深处遍历,都是遍历完一颗子树再遍历其他子树,所以又叫深度遍历。对于遍历方式还有另外一种,就是广度优先遍历,对应到二叉树里面就是层序遍历。先遍历完树的一层再遍历下一层。这种遍历方式没有往深处遍历到底,而是更关注广度的遍历。要实现这种遍历就需要使用到队列,事实上很多广度优先遍历都是用队列来实现,图的广度也是这样实现。

    void levelOrder(){
        queue<Node *> q;
        q.push(root);
        while (!q.empty()){
            Node *p = q.front();
            q.pop();
            cout << p->value;
            if (p->left){
                q.push(p->left);
            }
            if (p->right){
                q.push(p->right);
            }
        }
    }

这样很容易就实现了。二叉树的删除操作应该是属于二叉树操作里面比较难的部分,难的不是因为·删除本身,而是在于删除之后要怎么保持树的性质,所以是需要旋转。首先从一个最简单的问题开始,求二叉树最大值和最小值。

img_479df287424696aeee7f0ea3ab1351bd.png
因为左节点是比当前节点小的,右节点是比当前节点大的,所以找左节点就是不断往左边走,直到没有左孩子为止:

    Key minimum() {
        assert(count != 0);
        Node *node = minimum(root);
        return node->key;
    }

    Key maximum(){
        assert(count != 0);
        Node *node = maximum(root);
        return node->key;
    }

最大值和最小值都是一样。删除最小值,删除最小值有两种情况,如果这个最小值刚刚好没有任何节点,删除就很简单,如果是有的话那就需要一些操作了。


img_6cde776977a05b9049d15d948514af99.png

这种情况就很好删了,直接去掉即可。但是如果是有右孩子
img_faf1d998ebbc78bad44f6315a999ab11.png
这种情况删除最小的就需要做一些变化了,但也不是特别复杂,直接把右节点拉上来就好了,因为子树也是一颗二叉树。类似的思路删除最大值
img_c2d3b30b891922584fb6b6970a903d6f.png
这种情况删除最大值也是很简单的,直接扔了就好,但是如果是有左孩子的,直接把左边的子树拉上来就好了。
    Node *removeMax(Node *node){
        if (node->right == NULL){
            Node *left = node->left;
            delete node;
            count --;
            return left;
        }
        node->right = removeMax(node->right);
        return node;
    }

    Node *removeMin(Node *node){
        if (node->left == NULL){
            Node *right = node->right;
            delete node;
            count --;
            return right;
        }
        node->left = removeMin(node->left);
        return node;
    }

其实差不多的。最大值只会有左孩子,最小值只有右孩子。回到删除节点,对于只有右孩子,因为右孩子本来就大于当前节点,只有左孩子也是一样的。最难的就是左右孩子都有的情况,这样就尴尬了:

img_e61da26c890df9a864808b5abfa60e6d.png
如果是这种情况,我们就需要寻找当前节点的右孩子的作结点,找到
s = min(d->right)
,如果59没有那么就是删除60了,很明显,就是右子树的最小值了。

    Node *remove(Node *node, Key key){
        if ( node == NULL){
            return NULL;
        } else if (key < node->key){
            node->left = remove(node->left, key);
        } else if (key > node->key){
            node->right = remove(node->right, key);
        } else{
            if (node->left == NULL){
                Node *right = node->right;
                delete node;
                count --;
                return right;
            } else if (node->right == NULL){
                Node *left = node->left;
                delete node;
                count --;
                return left;
            } else{
                Node *delNode = node;
                Node *successor = new Node(minimum(node->right));
                count ++;
                successor->right = removeMin(node->right);
                successor->left = node->left;
                delete delNode;
                count --;
                return successor; 
            }
        }
    }

首先判断一下是不是只有左子树和右子树,如果只是有一边,那么可以直接把那一边拉上去,如果是两边都有,那就需要找到右边的最小值,代替要删除的节点。这里有一个陷阱,使用successor得到最小的节点之后,后面又删除了,这样就会得到一个空指针,我们只是要得到它并不是要删除,这个时候我们应该要复制一份过来,不能直接就拉过来。
以上的操作都是把二叉树当成一个查找表来实现的,但是二叉树还有一个很好的性质,二叉树是有很好的顺序性,所以二叉树不仅仅可以用来实现查找,还可以找最小值最大值,前驱后继等等。但是二叉树并不是一成不变的,各种元素的插入顺序的不同是可以导致二叉树的结构不一样,如果数据是基本有序的,插入基本就是一个链表的形状了,退化成了一个顺序链表。改进方法后面会提到红黑树AVL树这些更加高级的数据结构。

并查集

这个数据结构并不算高级的数据结构,但是在后面的图会用到来判断是否形成环,如果两个节点的根是相同的,那么就可以判断这两个节点是同一组的了,也就是已经连在了一起。之前的堆,二叉树都是树形的结构,而这个并查集也算是一种树形结构,但是和上述的两种不太一样。并查集可以解决的问题有很多,首先就是连接问题:

img_29df56230428d964dcc9449ecbea8754.png
想知道相邻两个点是不是连在一起的,如果这两个点是相邻的,沿着线可以很清楚的看到,但如果是一个左上角,一个右下角,那就很难看出来了。这种结构如果用并查集容易多了。连接可以应用在互联网之中好友之间的连接,一个人是否可以通过另外一个人认识另外一个人,这就是一种连接问题。
首先要知道一个并查集要支持什么操作,并查集主要支持两个操作,union,find,连接和查找操作。
用元素的下标是不是相同来表示这两个元素是不是连接的:
img_03806eed6cd84b76e42a7fa483967b2f.png
前面的一半就是一组,后面的一组又是一对。

class unionFind {
private:
    int *id;
    int count;
public:
    unionFind(int n) {
        count = n;
        id = new int(n);
        for (int i = 0; i < n; ++i) {
            id[i] = i;
        }
    }

    ~unionFind() {
        delete[] id;
    }

一开始大家都是各自为政,没有组团,所以都是不一样的,直接按照序列号即可。查找就是很简单了,就是直接返回id[]即可。

    int find(int p) {
        assert(p >= 0 && p <= count);
        return id[p];
    }

判断是不是连在一起的,直接找到当前属于的下标再比较即可,

    void unionElements(int p, int q){
        int pID = find(p);
        int qID = find(q);
        if (pID == qID){
            return;
        }
        for (int i = 0; i < count; ++i) {
            if (id[i] == pID){
                id[i] = qID;
            }
        }
    }

连接其实就是把两个堆连在一起,扫描下面的坐标相同的元素赋值即可,赋值那边赋值都可以。这种并查集查找很快,也叫quickUnion。

    UF_version1::unionFind uF = UF_version1::unionFind(10);
    uF.unionElements(1, 2);
    uF.unionElements(5, 4);
    uF.unionElements(3, 1);
    cout << uF.isConnected(4, 5) << endl;

上面这一种实现方法虽然实现查找的时候很快,但是实现并操作的时候很慢,需要进行遍历。并查集的另一种实现方式,而这种实现方式是后面实现并查集的一种常规实现方式。将每一个元素看成是一个节点,如果两个元素是一起的,那么这两个元素是一个指向另一个的。

img_c1d1cbb2e315df7f37129f6556fe10a3.png
这个时候2 3 1是指向了一起的,那么这三个就是一伙的,2是这个堆的根节点。
img_e311759829b9ddfa634f30e1901adc01.png
如果这两个堆要连在一起,那么只需要把他们的根连在一起就好了。
img_2b8af2d23ea4adb724cf7343ec0bccb9.png
如果一个元素指向另一个元素,那么他的下标就存那个被指向的元素。把6,3或者是7,3连接一起都是一样的,因为他们的根是一样的。要修改的其实就是find而已,其他都是差不多的。

        int find(int p){
            assert(p >= 0 && p <= count);
            while (parent[p] != 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;
            }
            parent[pRoot] = qRoot;
        }

不断向上找到自己的根,自己等于自己的就是当前的根了,如果不是就向下寻找,直到找到为止。这个时候的合并效率就不低了。注意到代码中的构造函数中有一个ecplicit,因为在c++中单个参数的构造函数是存在有隐式的转换的,加上这个关键字就可以禁止了,只能显示的构造,比如String = "Hello";就是一种隐式构造。
对于这种并查集,还是有优化空间的:

img_8d6405a337be60c94bdff8968b0a4537.png

比如这两个堆要和在一起,如果是9合到另外一个,
img_c1c260dce32fbb7c2c4c0761beef2eb2.png
这样做没有问题,但是这样查找效率不高。
img_538c54c3056a8cc19218900a8ac76a56.png
效果虽然是一样的,但是查找起来确比上面那种要快很多。比较之后哪一个小的就插入到大的那个上面去。

    private:
        int *parent;
        int *sz;
        int count;

增加一个sz的数组存储当前这个集合的数量,用于后面插入的比较,哪个大就插哪个。只要改变一下unionElements就好了,其他的不用变。

        void unionElements(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot) {
                return;
            }
            if (sz[pRoot] < sz[pRoot]){
                parent[pRoot] = qRoot;
                sz[qRoot] += sz[pRoot];
            } else{
                parent[qRoot] = pRoot;
                sz[pRoot] += sz[qRoot];
            }
        }

其实基于数量的优化还不是最优的,如果一个堆过于分散那么合并起来的效率不是很高的,所以还有一种改进方法,就是对比两者的层数插入即可。并查集的线路压缩,以上的插入很多时候有些随机的成分,如果对这个线路的结构进行调整会快很多。这种方法就叫路径压缩。

img_c5fb4731bda09a0de7632df83c16eb35.png
这种路径的查找明显是效率很低的,
img_6ba886dbba302e929edec251d03316b0.png
直观上进行调整,这样才是比较合理的。代码实现很简单,就是一句话的事情。

        int find(int p) {
            assert(p >= 0 && p <= count);
            while (parent[p] != p) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

没了,路径压缩就这样。当前节点指向他的根就好了,而find就是找到它的根。递归求解即可。在经过了路径压缩的优化之后查找的复杂度几乎就是O(1)复杂度了。

最后附上github地址:https://github.com/GreenArrow2017/DataStructure/tree/master/DataStucture

网友评论

登录后评论
0/500
评论
绿箭侠2017
+ 关注