文章目錄

• 解析
• 可以解決的問題
• • 定義：
  • 左偏樹的基本性質
  • 基本結論
• 操作
• • 合并
  • 訪問與刪除堆頂元素
  • 插入元素
  • 批量插入
  • 刪除已知元素

所謂左偏樹，就是往左偏的樹

下面介紹一下它的一個兄弟：

《右偏樹》
（逃）

解析

所謂左偏樹，確實就是往左偏的樹
它舍棄了平衡的性質，使這個堆在合并時變得極為高效
所以又叫做可并堆
代碼實現起來還是很好寫的

可以解決的問題

似乎基本上是起一個工具人的作用
出現在題解中“…對于某某信息，維護可并堆即可”這樣的地方
不會確實不行呀 qwq

定義：

外結點 ：左兒子或右兒子是空結點的結點。
距離 ： 一個結點 x 的距離 dist(x)定義為其子樹中與結點 x 最近的外結點到 x 的距離。特別地，定義空結點的距離為 -1 。

左偏樹的基本性質

左偏樹具有堆性質 ，即若其滿足小根堆的性質，則對于每個結點 x 有$v_x<v_{ls}$且$v_x<v_{rs}$
左偏樹具有 左偏性質 ，即對于每個結點 x ,有 $dis{t}_{lc}\ge dis{t}_{rc}$

基本結論

結點 x 的距離 $dis{t}_x=dis{t}_{rc}+1$
距離為 n 的左偏樹至少有 $2^{n+1}?1$個結點。此時該左偏樹的形態是一棵滿二叉樹。
有 n 的結點的左偏樹的根節點的距離是 $O({\log }_{2}n)$

（以上參考自：https://www.luogu.com.cn/blog/hsfzLZH1/solution-p3377）

上面的性質還是比較顯然的
下面我們來講講具體的操作

操作

合并

左偏樹的靈魂
設當前是小根堆，要把x堆與y堆合并
首先，如果x、y有一個為空，直接返回另一個
否則，把值較小的作為根，把根的右兒子與另一個堆合并
遞歸即可
遞歸回來的時候還要更新dist并維護左偏的性質
由于左偏樹極右鏈是不超過logn的
因此復雜度為logn
寫起來也很好寫

int merge(int x,int y){if(!x) return y;else if(!y) return x;if(val[x]>val[y]||(val[x]==val[y]&&id[x]>id[y])) 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; }

訪問與刪除堆頂元素

把堆頂的左右兒子合并并返回即可

int del(int &x){int res=val[x];x=merge(ls[x],rs[x]);return res; }

插入元素

把一個元素當成一棵樹，與大樹合并即可

void insert(int &r,int v){int x=New(v);r=merge(r,x); }

批量插入

直接插入n次nlogn
開一個隊列，把所有元素建成單點的樹push進去
每次從隊首提兩棵樹合并并放到隊尾
直至只剩下一棵樹
復雜度O(n)

void build(){queue<int>q;for(int i=1;i<=n;i++){q.push(New(a[i]));}for(int i=1;i<n;i++){int u=q.front();q.pop();int v=q.front();q.pop();q.push(merge(u,v));}r=q.front();q.pop(); }

刪除已知元素

這是一個左偏樹的重要優勢
它可以在logn的時間內刪除任意位置的已知元素
注意這里的“已知”是指已知編號而不是已知權值
刪除指定權值的操作是堆很難做到的 （至少對我的知識儲備來說）
注意樹的性質可能變，所以要一直往上更新

void Del(int x){int f=fa[x];int p=merge(ls[x],rs[x]);fa[p]=f;if(!f){r=p;return;}if(f&&ls[f]==x) ls[f]=p;if(f&&rs[f]==x) rs[f]=p;while(f){if(dis[ls[f]]<dis[rs[f]]) swap(ls[f],rs[f]);if(dis[f]==dis[rs[f]]+1) return;dis[f]=dis[rs[f]]+1;p=f;f=fa[f];}return; }

thanks for reading!

總結

以上是生活随笔為你收集整理的模板：左偏树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。