堆

每个节点权值大于（小根堆）父亲的树形数据结构。

以下均讨论小根堆的问题。

普通二叉堆

用数组 \(a[1\sim n]\) 构成一棵二叉树来维护堆操作，可以做到：

• 插入元素，

• 查询堆顶，

• 删除堆顶或者删除特定元素（需要记录权值位置）。

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. 合并两个堆：

直接按照堆顶权值大小合并，接上去即可。

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. 检查操作：

void Check(int x){
    if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
    dis[x]=dis[rs[x]]+1;
}

左偏树的合并操作即：

让较大的堆顶 和 小的堆顶的右儿子合并成为 新的右儿子。

很显然合并次数$\(两个堆的右儿子长度之和，这个操作是单次\)O(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)\)，因此可以对于每次合并得到的开一个新的节点存下来，即完成了可持久化操作