左偏树

# 左偏树 ## 1.[前置芝士](https://www.luogu.org/blog/donkey2603089141/post-dui) ## 2.定义 #### 1.左偏树(Leftist Tree)是一种可并堆(Mergeable Heap) ，它除了支持优先队列的三个基本操作（插入，删除，取最小节点），还支持一个很特殊的操作——合并操作。 #### 2.左偏树是一棵堆有序(Heap Ordered)二叉树。 #### 3.左偏树满足左偏性质(Leftist Property)。 ## 3.性质 定义一棵左偏树中的外节点(External Node) 为左子树或右子树为空的节点。 定义节点 i 的距离(dist(i)) 为节点 i 到它的后代中，最近的外节点所经过的边数。 #### 1.任意节点的左子节点的距离不小于右子节点的距离（左偏性质）。 #### 2.由左偏性质可知，一个节点的距离等于以该节点为根的子树最右路径的长度。 #### 3.节点的距离等于它的右子节点的距离加 1 #### 4.定理：若一棵左偏树有N个节点，则该左偏树的距离不超过 $\lfloor log(N+1) -1 \rfloor $ 。  ## 3.应用思路 ### 1.合并  将T1和T2两个可并堆进行合并，先将T1的右子树与T2合并。（a>b）  这个过程是递归的，如果合并之后右子树的距离大于左子树的距离我们就可以交换两者。 复杂度 $ O(log n) $ #### 代码 ```cpp int merge(int x,int y){ if(x==0||y==0) return x+y; if(v[x]>v[y]||(v[x]==v[y]&&x>y)) swap(x,y); ch[x][1]=merge(ch[x][1],y); fa[ch[x][1]]=x; if(dis[ch[x][1]]>dis[ch[x][0]]) swap(ch[x][1],ch[x][0]); dis[x]=dis[ch[x][1]]+1; return x; } ``` ### 2.插入 插入过程可以看做将一个节点的子树和原树合并，同上。 复杂度 $ O(log n) $ ### 3.删除 删除根节点 合并左右子树 复杂度 $ O(log n) $