【模板】左偏树

洛谷模板题

一听左偏树这个名字就感觉左偏。。

左偏树是什么，好像就是个堆，大根堆或小根堆，可以支持合并，取堆顶元素，删除堆顶元素，插入元素的操作。

一些说明：

左偏树节点除了应有的东西，还有键值和距离，键值用于比较大小，距离是什么？

距离是这样定义的：

节点i称为外节点(external node)，当且仅当节点i的左子树或右子树为空( left(i) = NULL或right(i) = NULL )；节点i的距离(dist(i))是节点i到它的后代中，最近的外节点所经过的边数。特别的，如果节点i本身是外节点，则它的距离为0；而空节点的距离规定为1 (dist(NULL) = 1)。一棵左偏树的距离，指的是该树根节点的距离。

额。。多看几遍才看懂。

左偏树具体有一些性质：

[性质1]节点的键值小于或等于它的左右子节点的键值。（键值就是点权）——堆的性质

[性质2]节点的左子节点的距离不小于右子节点的距离。——左偏

[性质3]节点的距离等于它的右子节点的距离加1。（因为左偏，所以右儿子距离小）

[引理1]若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。　　

[定理1]若一棵左偏树的距离为k，则这棵左偏树至少有2^k+11个节点。

[性质4]一棵N个节点的左偏树距离最多为?log(N+1)?1。(这是什么鬼？)

根据性质就可以理解左偏树操作的具体步骤了。

合并A和B：1.如果有一个树为空就返回另一个

　　　　　 2.假定root(A).w < root(B).w, 否则交换A和B，把root(A)作为新树的根

　　　　　 3.合并right(A)和B, 继续步骤2

　　　　　 4.由于合并之后right(A)的距离可能会变大, 如果变大就交换right(A)和left(A)

　　　　　 5.由于right(A)距离改变，A的距离也会变，更新dis(A) = dis(right(A)) + 1

1 //合并以 x, y 为根的堆 2 inline int merge(int x, int y) 3
合并

删除堆顶元素：删除后合并他的两个儿子即可

1 inline int pop(int x)//返回新合并的堆的堆顶 2
删除

取出堆顶元素：更智障

1 inline int top(int x)//第几个数所在堆的堆顶 2
取出

还有一些操作用到了并查集，具体细节看完整代码。

1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 int n, m; 7 int f[100001], l[100001], r[100001], w[100001], d[100001];//f[i]表示第i个数所在堆的堆顶 8 bool b[100001];//表示是否被删除 9 //合并以 x, y 为根的堆 10 inline int merge(int x, int y) 11 20 21 inline int pop(int x)//返回新合并的堆的堆顶 22 29 30 inline int find(int x) 31 34 35 inline int top(int x)//第几个数所在堆的堆顶 36 39 40 int main() 41 57 else 58 69 } 70 } 71 return 0; 72 }
View Code

上一篇：求逆序对（树状数组）

下一篇：[HDU2896]病毒侵袭（AC自动机）

---

模板 堆 左偏树