【左偏树】讲解

一、左偏树介绍

左偏树(Leftist Tree)是一种可并堆(Mergeable Heap) ，它除了支持优先队列的三个基本操作（插入，删除，取最小节点），还支持一个很特殊的操作——合并操作。

左偏树是一棵堆有序(Heap Ordered)二叉树。

左偏树满足左偏性质(Leftist Property)。

二、左偏树性质

定义一棵左偏树中的外节点(External Node)为左子树或右子树为空的节点。

定义节点 i 的距离(dist(i)) 为节点 i 到它的后代中，最近的外节点所经过的边数。

任意节点的左子节点的距离不小于右子节点的距离（左偏性质）。

由左偏性质可知，一个节点的距离等于以该节点为根的子树最右路径的长度。

定理：若一棵左偏树有N个节点，则该左偏树的距离不超过 [log(N+1) ]-1。( [ ] 这里是向下取整…因为打不出来了)。

三、左偏树的操作

3.1、合并

Function Merge(A, B)If A = NULL Then return BIf B = NULL Then return AIf key(A) > key(B) //保证小根堆的性质Then swap(A, B)right(A) ← Merge(right(A), B) //先将A的右子树与B合并If dist(right(A)) > dist(left(A)) //合并后的右子树距离可能大于左子树距离Then swap(left(A), right(A)) //交换左右子树//更新根节点距离If right(A) = NULL Then dist(A) ← 0Else dist(A) ← dist(right(A)) + 1return AEnd Function

合并操作都是一直沿着两棵左偏树的最右路径进行的。

一棵N个节点的左偏树，最右路径上最多有[ log(N+1) ] 个节点。

因此，合并操作的时间复杂度为：O(log N1 + log N2) = O(log N)

3.2、插入新节点

把待插入节点作为一棵单节点左偏树合并两棵左偏树时间复杂度：O(log N)

3.3、删除最小节点

删除根节点合并左右子树时间复杂度：O(log N)

四、左偏树的总结

1、左偏树的特点：（性价比高）

时空效率高编程复杂度低

2、左偏树的应用：（补充二叉堆的不足）

可并堆优先队列

五、模板

\\HYSBZ-2809#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <algorithm>#include <vector>using namespace std;const int maxn = 100010;struct heap{int l, r, d, w;} h[maxn];int n, m, rt[maxn], fa[maxn], sz[maxn];long long val[maxn], lead[maxn], sum[maxn], ans;vector<int> G[maxn];int Merge(int x, int y){if(!x || !y)return x + y;if(h[x].w < h[y].w)swap(x, y);h[x].r = Merge(h[x].r, y);rt[h[x].r] = x;if(h[h[x].l].d < h[h[x].r].d)swap(h[x].l, h[x].r);if(h[x].r)h[x].d = h[h[x].r].d + 1;elseh[x].d = 0;return x;}int Pop(int x){int l = h[x].l, r = h[x].r;rt[l] = l;rt[r] = r;h[x].l = h[x].r = h[x].d = 0;return Merge(l, r);}int top(int x){return h[x].w;}void dfs(int f){for(int i = 0; i < G[f].size(); i++){int u = G[f][i];dfs(u);rt[f] = Merge(rt[f], rt[u]);sum[f] += sum[u];sz[f] += sz[u];while(sum[f] > m){sum[f] -= h[rt[f]].w;sz[f]--;rt[f] = Pop(rt[f]);}}ans = max(ans, lead[f] * sz[f]);}int main(){while(~scanf("%d%d", &n, &m)){int root;ans = -1;for(int i = 1; i <= n; i++){scanf("%d%lld%lld", &fa[i], &val[i], &lead[i]);if(fa[i] == 0)root = i;G[fa[i]].push_back(i);h[i].d = h[i].l = h[i].r = 0;h[i].w = val[i];rt[i] = i;sz[i] = 1;sum[i] = val[i];}dfs(root);printf("%lld\n", ans);}return 0;}

如果觉得《【左偏树】讲解》对你有帮助，请点赞、收藏，并留下你的观点哦！