资讯详情

8/8

堆

priority_queue<int> q;
priority_queue<int,vector<int>,greater<int> > p;

上面是大根堆，下面是小根堆
可用操作：push,pop,top,size,empty

对顶堆

常用于维护动态第k大问题（平衡树也可以做到也说不了啥）

一个小根堆，一个大根堆，小根堆维护大于等于k的所有值，这样的话第k大就在堆顶，大根堆维护小于k的所有值，然后有一个维护操作，如果小根堆小于k，反复把大根堆堆顶加入小根堆，如果大于k，反复把小根堆堆顶推到大根堆，然后剩下的操作例如删除，添加之类的直接操作后进行维护就行了。

维护中位数的problem

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrep(i,a,b) for(int i=b;i>=a;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define inf 0x3f3f3f3f
#define fread freopen("input.txt","r",stdin)
#define fwrite freopen("output.txt","w",stdout)
#define readi read<int>()
#define readl read<ll>()
#define bs bitset<1010>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(){T x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
template<typename T>
inline void print(T x){if(x<0){putchar('-');x=-x;}if(x>9)print(x/10);putchar(x%10+'0');
}
priority_queue<int> q;
priority_queue<int,vector<int>,greater<int> > p;
int TT;
void check(){while(q.size()<p.size()){int tmp=p.top();q.push(tmp);p.pop();}while(p.size()+1<q.size()){int tmp=q.top();q.pop();p.push(tmp);}return ;
}
int main() {TT=readi;while(TT--){int op=readi;while(!q.empty()) q.pop();while(!p.empty()) p.pop();while(op!=0){if(op>0){if(q.empty() || op<=q.top()){q.push(op);}else{p.push(op);}check();}else if(op==-1){cout<<q.top()<<"\n";q.pop();check();}else{break;}op=readi;}// cout<<"大根堆："<<"\n";// for(int v:q) cout<<v<<" ";// cout<<endl;// cout<<"小根堆"<<"\n";// for(int v:p) cout<<v<<' ';}debug("Time: %.3lf\n", double(clock()) / CLOCKS_PER_SEC);return 0;
}

这个代码是用大根堆为存储中位数的方法去做的，代码就是上面的，注意多测清空以及到底是用大于小于号

可并堆

配对堆

就是改变一下堆的结构，但改变后也是树
同一深度的val是兄弟节点，父亲节点连接最左端的兄弟节点，兄弟节点之间建边，其余子树也同理。
这样的结构可以暴力的去合并以及插入，两个堆里取较小点作为根节点，可以用指针做。
那么删除操作就要复杂一点，我们考虑第一遍的每两个先合并为较大的，然后线性的去合并，可以证明复杂度均摊O(log n)
然后是减小一个值，如果是根节点对于小根堆来说减少是不劣的，如果是儿子节点的话，直接拆开然后重新合并即可。

实现没有写，可以