堆模板
⼀些堆的总结
1.⼆叉堆
这个是最简单的堆，⽤于维护最⼤最⼩值。⽀持删除，弹出堆顶节点，查询最⼤值（或优先级最⾼的节点）
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN =1000001;
struct Node{
int Val;
bool operator<(const Node &a)const{
return Val > a.Val;//重载⼩于号
}
}h[MAXN];
struct Binary_Heap{
int HeapSize;
inline void push(int v){
int u =++HeapSize, fa; h[HeapSize].Val = v;
while(u >1){leftist
fa = u >>1;
if(h[u]< h[fa])break;//该节点优先级⼩于其⽗亲
swap(h[u], h[fa]);
u = fa;
}
}
inline int top(){
return h[1].Val;
}
inline void pop(){
int u =1; h[1]= h[HeapSize--];
while((u <<1)<= HeapSize){
int Son = u <<1;
if(Son +1<= HeapSize && h[Son]< h[Son +1]) Son++;
if(h[Son]< h[u])break;
swap(h[u], h[Son]);
u = Son;
}
}
}Heap;
2.优先队列
这个是STL⾥的东西，众所周知，STL模板常数⼤但泛⽤，好写
上⾯的代码就可以变成这个：
#include<queue>
#include<algorithm>
using namespace std;
struct Node{
int Val;
bool operator<(const Node &a)const{
return Val > a.Val;//重载⼩于号
}
};
priority_queue <Node> Heap;
3.左偏树/EX并查集（⼤雾
左偏树在⼀般的⼆叉堆基础之上，还⽀持合并操作。
配合⾷⽤
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN =1000001;
int val[MAXN], fa[MAXN], ch[MAXN][2], dis[MAXN];
struct Leftist_Tree{
int Merge(int x,int y){
if(!x ||!y)return x + y;
if(val[x]> val[y])swap(x, y);
else if(val[x]== val[y]&& x > y)swap(x, y);
ch[x][1]=Merge(ch[x][1], y); fa[ch[x][1]]= x;
if(dis[ch[x][0]]< dis[ch[x][1]])swap(ch[x][0], ch[x][1]);
dis[x]= dis[ch[x][1]]+1;
return x;
}
inline int top(int t){
while(fa[t]) t = fa[t];
return t;
}
inline void pop(int t){
val[t]=-1;
fa[ch[t][0]]= fa[ch[t][1]]=0;
Merge(ch[t][0], ch[t][1]);
}
}Heap;
inline int read(){
int k =0;char ch =getchar();
while(ch <'0'|| ch >'9') ch =getchar();
while(ch >='0'&& ch <='9'){k = k*10+ ch -'0'; ch =getchar();} return k;
}
int main(){
int n =read(), m =read();
for(int i =1; i <= n; i++) val[i]=read();
for(int i =1; i <= m; i++){
int opt =read(), x, y;
if(opt ==1){
x =read(), y =read();
if(val[x]==-1|| val[y]==-1)continue;
x = p(x), y = p(y);
if(x == y)continue;
Heap.Merge(x, y);
}
else{
x =read();
if(val[x]==-1){printf("-1\n");continue;}
x = p(x);
printf("%d\n", val[x]);
Heap.pop(x);
}
}
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。