堆
每个节点权值大于(小根堆)父亲的树形数据结构
以下均讨论小根堆的问题
普通二叉堆
用数组(a[1:n])构成一棵二叉树来维护堆操作，可以做到
1.插入元素
2.查询堆顶
3.删除堆顶或者删除特定元素(需要记录权值位置)
1.插入元素
先放到(a[n+1])的位置，然后每次与父亲比较是否交换
void push(int x){
a[++n]=x;
for(int p=n;p>1 && a[p]<a[p>>1];) swap(a[p],a[p>>1]),p>>=1;
}
2.删除特定元素
删除后，把(a[n])元素放到空的位置，然后向下走，注意每次一定是把左右儿子中比较小的换上来
void Delete(int x){
swap(a[x],a[n--]);
for(int p=x;(p<<1)<=n;){
int nxt=p<<1;
if((p<<1|1)<=n && a[p<<1|1]<a[p<<1]) nxt=p<<1|1;
if(a[nxt]<a[p]) swap(a[p],a[nxt]);
else break;
}
}
配对堆
配对堆不是一个二叉树结构，所以在存储上，使用左儿子右兄弟来存储树形结构
可以实现的操作有
1.插入/删除元素，查询堆顶
2.查询堆顶
3.合并两个堆
首先要维护最基本的两个操作
1.合并两个堆
直接按照堆顶权值大小合并，接上去即可
int a[N],ch[N],br[N]; //权值，儿子，兄弟
int Union(int x,int y){
if(!x||!y) return x|y;
if(a[x]>a[y]) swap(x,y);
br[y]=ch[x],ch[x]=y;
return x;
}
2.配对操作
把一个点的所有儿子两两合并之后再依次合并到一起
配对堆的所有操作都基于合并和配对实现
合并操作是(O(1))的
配对操作单次最坏是(O(n))，但是和(Splay)类似的，配对可以让儿子中兄弟最多的个数减半，是一个均摊(O(log n))的操作，因此不可持久化，但是实际运行常数比较小
操作实现：用一个函数给(x)和(x)的右边的所有兄弟配对，递归实现
每次让(x)和右边第一个兄弟配对(即先合并)，再和右边剩下的节点合并
int Pair(int x){
if(!x || !br[x]) return x;
int y=br[x],z=br[y];
return Union(Union(x,y),Pair(z));
}
3.删除元素
如果删除的不是堆顶元素，还需要额外存储每个点的父亲
把被删除元素的儿子合并之后接到父亲上面
4.查询堆顶
如果是查询某个特定元素所在堆的堆顶，需要用并查集来维护
左偏树
左偏树是一个二叉堆结构，顾名思义，向左边偏的树
左偏树判断左偏的方法是定义了一个(dis)数组，满足(forall dis_{lson}ge dis_{rson},dis_x=dis_{rson}+1)
因此一直走右儿子的链长度就是(O(log n))的
利用这个性质完成操作，每次合并之后检查(dis_{lson},dis_{rson})是否满足条件
可以完成的操作有
1.插入节点/合并堆
2.删除节点
3.访问堆顶
4.可持久化
1.检查操作
void Check(int x){
if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
dis[x]=dis[rs[x]]+1;
}
左偏树的合并操作就是
让较大的堆顶 和 小的堆顶的右儿子合并成为 新的右儿子
很显然合并次数$leq (两个堆的右儿子长度之和，这个操作是单次)O(log n)$
int Union(int x,int y){
if(!x||!y) return x|y;
if(a[x]>a[y]) swap(x,y);
return rs[x]=Union(rs[x],y),;
}
2.删除节点
合并左右儿子后接到父亲上
3.访问堆顶
左偏树的深度没有保证，访问特定节点所在堆的堆顶需要用并查集维护
4.可持久化
由于单次访问复杂度保证了是(O(log n))，因此可以对于每次合并得到的开一个新的节点存下来
即完成了可持久化操作