环球今亮点！左偏树学习笔记

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

环球今亮点！左偏树学习笔记

2023-01-05 22:57:31 来源：博客园

左偏树是一类拥有下列操作的数据结构：

插入一个数 \(O(log n)\)
求最小值 \(O(1)\)

(资料图片仅供参考)
删除一个节点 \(O(log n)\)
合并两棵树 \(O(log n)\)

左偏树本身具有堆的性质，又称为可并堆。

以维护最小值为例：

概念：

权值\(val\)
距离\(dis\)：到最近的根节点的距离（\(\leqslant log n\)）

\(left\rightarrow dist\rightarrow right\rightarrow dist\)

\(f[k]\)：距离为\(k\)的子树，至少包含多少个点。

\(f[k]\geqslant 2^k-1\)证明：\(k=1,n=k-1\)\(n=k, f(n)\geqslant 2^{k-1}-1+2^{k-1}-1+1=2^k-1\)故必须要有\(f[k]\geqslant 2^k-1\)

\(merge(a,b)\)：合并子树\(a,b\)，并返回合并后的根节点。比较\(a,b\)的根节点的大小，如果\(a\)的根节点小于\(b\)的根节点，则把\(b\)插到\(a\)的右子树，然后检查\(a\)是否符合左偏性质，如果不满足就把左右子树交换。这个操作存\(root\)时需要路径压缩。为什么可以用并查集？只有合并而没有分裂。

于是下面的操作就很简单了。

插入操作：建立只包含一个点的左偏树，将其与原树合并。最小值：根节点删除操作：合并左右子树。

code

bool cmp(int x, int y){    if (v[x] != v[y]) return v[x] < v[y];    return x < y;}int find(int x){    if (p[x] != x) p[x] = find(p[x]);    return p[x];}int merge(int x, int y){    if (!x || !y) return x + y;    if (cmp(y, x)) swap(x, y);    r[x] = merge(r[x], y);    if (dist[r[x]] > dist[l[x]]) swap(l[x], r[x]);    dist[x] = dist[r[x]] + 1;    return x;}

习题选做：P4359 【CQOI2016】伪光滑数P3261 【JLOI2015】城池攻占

关键词：求最小值节点删除数据结构

环球今亮点！左偏树 学习笔记

环球今亮点！左偏树学习笔记