猫史档案馆

栈和队列这种非常简单的就没必要讲了，用kitten都能很快做出来。关于栈的话，大家可以搜搜我的“kitten高阶教程”的那个。如果要了解队列，可以看看Max（就是无情的AC自动鸡）神犇的帖子。（路卡西欧的就算了，讲的并不好）

博客食用更佳：https://www.luogu.com.cn/blog/Jazzq13957122928/post-dui-you-xian-dui-lie-di-li-xie

数据结构

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。
简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。
“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

堆

堆，又叫优先队列(priority_queue)。是一棵具有堆性质的完全二叉树。

堆的构成方法：对于每一个属于该堆的节点x，都满足 x 的值是以 x 为根的子树中每个节点的值的最大（最小）值。

很显然，堆的最大（最小）值在树的根结点上。

如果根是最大值，那么就叫 大根堆 。如果根是最小值，那么就叫 小根堆 。

STL中的优先队列

插入的数会自动排成从大到小的顺序。

优先队列能在很短的时间内将插入后的序列重新排好顺序。

比如 Dijkstra 算法的堆优化就可以用优先队列实现。

具体使用

使用以下头文件

#include<queue>

以及加入这一行调用std名字空间

using std::priority_queue;

定义如下（std模板库默认为大根堆）

priority_queue<int>Q;//定义一个int类型的叫做Q的堆（优先队列）

下面给出一些常用函数

Q.push(a);
//将a插入堆中

x=Q.top();
//获取堆顶元素

Q.top();
//删除堆顶元素

x=Q.size();
//获取堆的长度

while(!Q.empty())Q.pop();
//清空堆

需要注意的是，堆（优先队列）是默认为大根堆的。所以不能存储小根堆。

怎么办？

(凉拌)(更新C++)

方法就是存入每个元素之前都先取负。这样就行了。

例题

初始一个小根堆为空，支持以下操作：

1：1x表示将x插入堆中

2：2表示输出堆最小数

3：3表示删除堆顶元素

输入第一行一个整数N，表示操作的个数。接下来N行，表示三种操作。

输出若干整数，每行对应一个操作2的结果。

只需要STL priority_queue就行了。注意小根堆要取负。

int opt,x;
cin>>n;
while(n--){
    cin>>opt;
    if(opt==1)cin>>x,Q.push(-x);//小根堆，要取负
    else if(opt==2)cout<<-Q.top();//取出元素的时候符号改回来
    else Q.pop();
}

并查集

集合相关概念及定义

集合是高一必修一里面的内容（人教版）。教材里面讲了很多很多实际上是给函数的定义做个铺垫。下面我总结一下。

集合(aggregate)，是由确定的元素构成的整体。集合中的元素有如下特征：

确定性：一个元素要么属于这个集合，要么不属于。

互异性：集合中的每个元素互不相同。

无序性：元素没有优先顺序。

假设有实数x < y：

①[x，y] ：方括号表示包括边界，即表示x到y之间的数以及x和y；

②(x，y)：小括号是不包括边界，即表示大于x、小于y的数。

交集定义：由属于A且属于B的相同元素组成的集合，记作A∩B（或B∩A），读作“A交B”（或“B交A”），即A∩B={x|x∈A,且x∈B}，如右图所示。注意交集越交越少。若A包含B，则A∩B=B，A∪B=A

并集定义：由所有属于集合A或属于集合B的元素所组成的集合，记作A∪B（或B∪A），读作“A并B”（或“B并A”），即A∪B={x|x∈A,或x∈B}，如右图所示。注意并集越并越多，这与交集的情况正相反。

并查集

一般来讲，存储集合的方法有数组存储、链表存储、森林存储等。

数组存储和链表存储就不讲了。下面着重讲一下森林存储。

注意到一个元素值可能属于一个集合，所以我们可以为每一个集合G选取一个代表元w(G)。于是查询u,v是否属意一个集合，实际上是询问是否w(U)=w(V)。

因此，对于每个元素，维护它所属集合的代表元，询问时直接比较即可。

那么如何合并？

注意到合并的时间复杂度远高于查询。我们可以用森林来维护代表元。对于每一个元素x，维护其父亲fa[x]。对于一个集合的代表元，有fa[x]==x。一开始每个元素都是其所在集合的代表元，即fa[x]=x。当要合并u、v所在集合时，找到w(U)和w(V)，然后建立父子关系，即

fa[w(U)]=w(V)
或
fa[w(V)]=w(U)

因此，我们很容易地能写出代码。

int dsu[maxn];
void init(){
    for(int i=1;i<=n;i++)
        dsu[i]=i;
}
int find(int pos){
    if(dsu[pos]==pos)return pos;
    else return find(dsu[pos]);
}
void merge(int x,int y){
    dsu[find(x)]=find(y);
}

不幸的是，该方法不是最优的。

优化1：维护集合的大小，合并时将较小的并入较大的。

优化2：路径压缩。

Code：

int dsu[maxn],size[maxn];
void init(){
    for(int i=1;i<=n;++i)dsu[i]=i,size[i]=1;
}
int find(int pos){
    if(dsu[pos]==pos)return pos;
    else return dsu[pos]=find(dsu[pos]);
}
void merge(int x,int y){
   x=find(x);y=find(y);
   if(size[x]<size[y])swap(x,y);
   dsu[y]=x;size[x]+=size[y];
}

例题

现在有一个并查集，你需要完成合并和查询操作。

输入第一行包含两个整数 N,M,表示共有 N 个元素和 M 个操作。

接下来 MM 行，每行包含三个整数 Zi,Xi,Yi 。

当 Zi=1 时，将 Xi 与 Yi 所在的集合合并。

当 Zi=2 时，输出 Xi 与Yi 是否在同一集合内，是的输出 Y ；否则输出 N 。

并查集模板。是对上面的总结。

//用到了启发式合并优化和路径压缩
int i,j,k,n,m,s,ans,f[10010],p1,p2,p3;
//f[i]表示i的集合名
int find(int k){
	//路径压缩
    if(f[k]==k)return k;
    return f[k]=find(f[k]);
}
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++)
        f[i]=i;//初始化i的代表元为自己
    for(i=1;i<=m;i++){
        cin>>p1>>p2>>p3;
        if(p1==1)
            f[find(p2)]=find(p3);
            //p3比p2大，p2并入p3
        else
            if(find(p2)==find(p3))
            //是否属于同一集合
                printf("Y\n");
            else printf("N\n");
    }
    return 0;
}

猫史档案馆

【C++OI基础教程】数据结构教程详解（一）

回复