左偏樹

左偏樹是一種可以讓我們在 \(O(\log n )\) 的時間複雜度內進行合併的堆式資料結構。

為了方便以下的左偏樹為小根堆來討論。

定義

外結點：左兒子或者右兒子是空節點的結點。

距離：一個結點 \(x\) 的距離 \(dis[x]\) 定義為其子樹中與結點 \(x\) 最近的外結點到 \(x\) 的距離。定義空節點的距離為 \(-1\)。

性質

• 左偏樹具有堆性質，即若滿足小根堆的性質，則對於每一個結點 \(x\)，都有 \(w[x]\le w[ls[x]],w[x]\le w[rs[x]]\)。其中 \(w\) 為權值，\(ls,rs\) 為左兒子，右兒子。

• 左偏樹具有左偏的性質，即對於每一個點 \(x\)，都有 \(dis[ls[x]]\ge dis[rs[x]]\)。

基本結論

結點 \(x\) 的距離 \(dis[x]=dis[rs[x]]+1\)，很明顯上面說過的性質裡面可以看出右兒子的距離更小，所以我們在計算當前結點的 \(dis\) 時應該用更小的 \(dis[rs]\)。

距離為 \(n\) 的左偏樹至少有 \(2^{n+1}-1\) 個結點，此時該左偏樹的形態是一棵滿二元樹。

操作

合併

左偏樹的很多操作都是需要用到合併操作的。

我們用 merge(x,y) 來表示合併兩棵以 \(x,y\) 為根節點的左偏樹，其返回值就是合併之後的根節點的編號。

首先如果要是不考慮左偏的性質，假設我們合併的是小根堆：

1. 若 \(w[x]\le w[y]\)，以 \(x\) 作為合併後的根節點；否則以 \(y\) 作為合併後的根節點。為了避免討論，若有 \(w[x]>w[y]\) 我們就 swap 一下。

2. 將 \(y\) 與 \(x\) 的其中一個兒子合併，用合併後的根節點代替與 \(y\) 合併的兒子的位置，並返回 \(x\)。

3. 重複以上操作，如果 \(x,y\) 有一個是 \(0\)，就返回 \(x+y\)，也就是返回不為 \(0\) 的結點的編號。

當然上述的方法在資料為一條鏈的時候會 T 飛，所以我們需要讓他左右保持一個相對平衡的狀態，這個時候我們就有了左偏樹（當然平衡樹也可以）。

由於我們前面說過左偏樹中左兒子的距離大於右兒子的距離，我們每次將 \(y\) 與 \(x\) 的右兒子合併，由於左偏樹的樹高為 \(\log n\) 的，所以單次合併的複雜度也為 \(O(\log n)\)。

但是，兩棵左偏樹按照上述方法合併後，可能不再保持左偏樹的左偏性質。在每次合併完之後，判斷對結點 \(x\) 是否有 \(dis[ls[x]]\ge dis[rs[x]]\)，若沒有則交換 \(ls,rs\)，並維護 \(x\) 的距離 \(dis[x]=dis[rs[x]]+1\)，即可維護左偏樹的左偏性質。

插入給定值

我們可以直接新建一個點，然後將他和左偏樹合併就好。

求最小（大）值

由於滿足堆的性質，所以我們直接返回堆頂的元素就好。

刪除最小（大）值

也就是刪除堆頂元素，直接合並根節點的左右兒子即可。

刪除任意結點

inline void del(int x)
{
	int tmp=merge(ls[x],rs[x]),fu=fa[x];
	f[tmp]=fa[tmp]=fu;
	f[x]=fa[x]=tmp;
	ls[fu]==u?ls[fu]=tmp:rs[fu]=tmp;
	while(fu)
	{
		if(dis[ls[fu]]<dis[rs[fu]])swap(ls[fu],rs[fu]);
		if(dis[fu]==dis[rs[fu]]+1)return ;
		dis[fu]=dis[rs[fu]]+1;
		fu=fa[fu];
	}
}

這裡 \(fa\) 是父節點。

我們和刪除根節點一樣先合併子樹，然後存起來刪除的點的父節點 \(fu\)。

然後合併後的點的父節點和所屬點先設為 \(fu\)，然後我們把刪除了的給調整成父節點和所在左偏樹根節點為合併後的結點。

然後判斷刪除的點是父節點的左兒子還是右兒子然後用合併後的替換。

然後我們從父節點不斷向上更新 \(dis\) 並用 swap 來維護左偏性質即可。

求給定結點所在的左偏樹的根節點

我們可以開個陣列 \(f\) 來記錄父節點然後每次詢問暴力跳，但是複雜度太高。

我們思考一下，我們可以像並查集一樣採用路徑壓縮的辦法來讓這個複雜度變低。

在合併兩個結點的時候，令 f[x]=f[y]=merge(x,y)。

在刪除左偏樹中的最值時，我們令 f[ls[x]]=f[rs[x]]=f[x]=merge(x,y)，因為 \(x\) 是之前左偏樹的根節點，在路徑壓縮的時候可能有 \(f\) 的值等於 \(x\)，所以 \(f[x]\) 也要指向刪除後的根結點。

【模板】左偏樹（可並堆） - 洛谷

code：

#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,m,ls[N],rs[N],dis[N],f[N],vis[N];
struct sb{int id,w;bool operator<(sb x)const{return w==x.w?id<x.id:w<x.w;}}e[N];
inline int fid(int x){if(x==f[x])return x;return f[x]=fid(f[x]);}
inline int merge(int x,int y)
{
	if(!x||!y)return x+y;
	if(e[y]<e[x])swap(x,y);
	rs[x]=merge(rs[x],y);
	if(dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]);
	dis[x]=dis[rs[x]]+1;
	return x;
}
signed main()
{
	dis[0]=-1;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  cin>>e[i].w,f[i]=i,e[i].id=i;
	for(int i=1;i<=m;i++)
	{
		int op,x,y;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y;
			if(vis[x]||vis[y])continue;
			int xx=fid(x),yy=fid(y);
			if(xx==yy)continue;
			f[xx]=f[yy]=merge(xx,yy);
		}
		else
		{
			cin>>x;
			if(vis[x]){puts("-1");continue;}
			int xx=fid(x);
			cout<<e[xx].w<<endl; 
			vis[xx]=1;
			f[ls[xx]]=f[rs[xx]]=f[xx]=merge(ls[xx],rs[xx]);
			ls[xx]=rs[xx]=dis[xx]=0;
		}
	}
	return 0;
}

參考：https://www.luogu.com.cn/blog/hsfzLZH1/solution-p3377