【算法】高级数据结构

并查集

并查集简要来说就是一个聚类操作，然后选区类里面的一个元素作为代表，用于将一类的元素划分到一个集合当中。

例题

并查集标程，并查集的构造需要三个核心功能：

初始化并查集
合并元素集合
查找集合代表元素

如何查有多少个集合：直接 for 循环遍历，查找有多少个 s[i]=i ，就有多少个集合

问2，查找，合并的复杂度是多少：
合并操作的复杂度其实就是查找的复杂度，查找最坏情况下要遍历所有的节点，所以是$O(n)$

标程代码

#include<iostream>
using namespace std;
int s[5001];
int n,m,p;
void init(){
    for(int i=1;i<=n;i++){
        s[i]=i;
    }
}
int find_set(int x){
    return x==s[x]?x:find_set(s[x]);
}
void union_set(int x,int y){
    int xroot = find_set(x);
    int yroot = find_set(y);
    if(xroot!=yroot){
        s[xroot] = s[yroot];
    }
}

int main(){
    cin>>n>>m>>p;
    init();
    int a,b;
    while(m--){
        cin>>a>>b;
        union_set(a,b);
    }
    while(p--){
        cin>>a>>b;
        if(find_set(a)==find_set(b)){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

以上代码中的并查集操作实际上是比较低效的，可以通过优化来达到更高效的操作，以下是一些优化步骤：

优化合并操作

由于在上面的代码中，我们都把集合赋值给y 那一方，导致出现这样一种状况，可能把高度较大的树并到了高度较小的树当中，导致原本高的那颗树又加 1 层，变得更高，查找时就更慢。我们可以优化这种操作，让他把高度较小的树并到高度较大的树中

具体代码实现：

int height[5001];
void init(){
    for(int i=1;i<=n;i++){
        s[i]=i;
        height[i]=0;
    }
}
void union_set(int x,int y){
    int xroot = find_set(x);
    int yroot = find_set(y);
    // 对于树高一样的，合并后会增加一层树的高度
    if(height[xroot] == height[yroot]){
        height[xroot] = height[xroot] + 1;
        s[yroot] = xroot;
    }
    // 对于树高不一样的，把小树并到大树中，高度还是大树的高度保持不变
    else{
        if(height[xroot] < height[yroot])
            s[xroot] = s[yroot];
        else
            s[yroot] = s[xroot];
    }
}

优化查询操作

在查询过程中，我们是沿着节点一个个递归往回查找的，如果在递归回去的过程中，我们可以把递归最后一层的结果往回传递，来更新查询路径，如下

具体实现代码

int find_set(int x){
    if(s[x]!=x){
        s[x] = find_set(s[x]);
    }
    return x;
}

二叉树

概念

二叉树就是每层每个节点最多有两个子节点：左孩子和右孩子。如果每一层的节点数都是满的，称为满二叉树。如果保持严格从左到右的顺序添加节点，且只在最后一层有缺失，称为完全二叉树

遍历

二叉树有三种常见的遍历方式

先序遍历：按照父结点->左孩子->右孩子的顺序遍历
中序遍历：按照左孩子->父结点->右孩子的顺序遍历
后序遍历：按照左孩子->右孩子->父结点的顺序遍历

代码就不列出了，就是简单的递归，取决于把 cout 放在哪里罢了。

这里如果只知道先序遍历与后序遍历，是不能确定一棵树的，下面这种分支，先序和后序的结果都一样

已知先序和中序如何还原树：

已知中序和后序的还原过程也和上面类似。

例题

标程

#include<iostream>
#include<cstdio>
using namespace std;
int n;
struct treenode{
    int l,r;
}node[1000010];

inline void preorder(int t){
    cout<<t;
    if(node[t].l) preorder(node[t].l);
    if(node[t].r) preorder(node[t].r);
}

inline void inorder(int t){
    if(node[t].l) inorder(node[t].l);
    cout<<t;
    if(node[t].r) inorder(node[t].r);
}

inline void postorder(int t){
    if(node[t].l) postorder(node[t].l);
    if(node[t].r) postorder(node[t].r);
    cout<<t;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        if(a) node[i].l = a;
        if(b) node[i].r = b;
    }
    preorder(1);
    cout<<endl;
    inorder(1);
    cout<<endl;
    postorder(1);
    cout<<endl;
    return 0;
}

一些小细节，这里使用了内联函数 inline，内联函数请求编译器在每个调用点直接替换该函数的代码，而不是正常的调用函数的过程，他会嵌入主函数当中，可以减少频繁调用函数所产生的开销，这里是有一些使用条件的，由于这几个遍历方式所带来的代码体量小，不会显著增大主函数的代码量，并且递归是频繁调用的，所以使用内联函数可以节约很多调用所带来的开销。

堆

堆的概念

堆是一个树形结构，是一颗完全二叉树，严格满足根节点是整颗树的最大或者最小值，同时各个父结点的值比孩子节点的值大或者小（取决于是大根堆还是小根堆）。

插入元素

堆的插入操作，就是把要插入的元素先放到数组末尾，然后在按照堆的规则往上跳

复杂度是 $O(logn)$ 因为是按照树的层级往上跳的

删除元素

元素的删除，就把叶子节点的元素覆盖到那个节点，如果是根节点，把覆盖后的节点下沉，如果是非根节点，还要考虑会上移（比如小根堆中，这个叶子节点可能比覆盖的节点还小）。

例题

代码

#include<iosream>
using namespace std;
const int MAXN = 100010;
int len = 0;
int heap[MAXN+1];

//下沉操作
void down(int k){
    while(2*k<=len){
        int node = 2*k; //左孩子
        //选择小的那个孩子
        if(node+1<=len&&heap[node]>heap[node+1]){
            node += 1; //右孩子
        }
        if(heap[k] <= heap[node]) break;
        swap(heap[k],heap[node]);
        k = node;
    }
}
//上浮操作
void up(int k){
    while(k>1&&heap[k/2]>heap[k]){
        swap(heap[k],heap[k/2]);
        k/=2;
    }
}

//插入
void insert(int x){
    heap[++len] = x;
    up(len);
}


//堆弹出
void pop(){
    swap(heap[1],heap[len]);
    len--;
    down(1)
}

int main(){
    int n;
    cin>>n;
    len=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        insert(x);
    }
    for(int i=1;i<=n;i++){
        cout<<heap[1]<<" ";
        pop();
    }
}

再来看一道例题

求中位数，最简单的方法就是用插入排序，每次插入排序后长度为奇数时，输出他的中间数即可。

如果用堆去做，可以将堆分为一个大根堆和一个小根堆，满足小根堆的根节点大于大根堆的根节点，这样就可以把数组等分成两个部分，然后用大根堆的根去存储中位数即可。

这里需要注意的是，堆也是需要动态调整的，如果一直出现很小的数，就会一直往大根堆里放，导致不等分，所以有两种情况：

小根堆不能比大根堆多，因为中位数是大根堆的根节点
大根堆不能比小根堆多 3 个元素以上（包括 3 个元素）这样的话就不平衡了

代码

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int> que1; //大根堆
priority_queue<int,vector<int>,greater<int>> que2; //小根堆

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=(n-1)/2;i++){
        int x;
        cin>>x>>y;
        int mid = que2.top();
        if(x>=mid){
            que2.push(x);
        }
        else{
            que1.push(x);
        }
        if(y>=mid){
            que2.push(y);
        }
        else{
            que1.push(y);
        }
        if(que2.size()>que1.size()){
            que1.push(que2.top());
            que2.pop();
        }
        else if(que1.size()-que2.size()==3){
            que2.push(que1.front());
            que1.pop();
        }
        cout<<que1.top()<<endl;
    }
}