可并堆（左高树、左偏树）

左偏树相对于二叉堆，其插入，弹出，合并的时间复杂度都是对数级别的。

高度优先左偏树（HBLT）

考虑一颗二叉树，将其叶子节点的子节点补全，那么原来有的节点叫做内部节点，新增加的节点叫做外部节点。

令s(x)s(x)s(x)，等于节点xxx到任意外部节点的最短路径的长度。外部节点的s(x)s(x)s(x)的值为000，叶子节点的值为111。其递归定义为：

s(x)=min⁡{s(L),s(R)}+1s(x) = \min\{s(L),s(R)\} + 1s(x)=min{s(L),s(R)}+1

定义一颗高度优先左偏树为，当且仅当其任意内部节点的左孩子的s(L)s(L)s(L)都大于等于右孩子的s(R)s(R)s(R)。

一颗高度优先左偏树有如下定理：

以xxx为根的子树的节点数目至少为2s(x)−12^{s(x)}-12s(x)−1以xxx根的子树节点有mmm个，那么s(x)s(x)s(x)至多为log⁡2(m+1)\log_2(m+1)log2​(m+1)从xxx节点一直往右孩子走，直到外部节点的路径长度为s(x)s(x)s(x)高度优先左偏树是递归定义的，两个左右孩子仍然是高度优先左偏树

定义一颗二叉树既是高度优先左偏树，又是大根树，则称为最大HBLT。同理，如果同时是小根树，则称为最小HBLT。最大，最小队列可用最大最小HBLT表示。

插入

将一个数值插入一个左偏树中，由于一个节点也是左偏树，那么就相当于合并两个左偏树。

弹出

将根节点的两个左右子树进行合并，将合并后的根节点作为新的根节点。并删除原来的根节点。

合并

合并的过程是一直沿着两棵树的右路径进行合并。首先比较两个左偏树的根节点，选择权值大的那个作为合并后的根节点，并将另外一个左偏树和根节点的右节点进行递归合并。将合并后的右子树的根节点作为新的根节点，然后根据定义s(x)s(x)s(x)查看是否需要交换两个子树，最后更新根节点的s(x)s(x)s(x)的值。

线性初始化

如果我们依次插入新的节点，时间复杂度是O(nlog⁡n)O(n\log n)O(nlogn)的。我们建立一个队列，首先将节点大小为111的节点插入到队列中。每次从队首中选择两个左偏树进行合并。直到队列的大小为111。此时是时间复杂度是O(n)O(n)O(n)的。

重量优先左偏树（WBLT）

重量优先左偏树和高度优先左偏树的定义基本类似，其s(x)s(x)s(x)的定义为以xxx为根节点的子树的节点数。

其他操作和高度优先左偏树完全一致。

P3377

#include <bits/stdc++.h>#define FR freopen("in.txt", "r", stdin)#define FW freopen("out.txt", "w", stdout)using namespace std;typedef long long ll;struct Node{int id;int val;int s;int l;int r;} nodes[300005];int tot = 0;int createNode(int val){tot++;nodes[tot].id = tot;nodes[tot].s = 1;nodes[tot].val = val;return tot;}int merge(int u, int v){if (u == 0)return v;if (v == 0)return u;if ((nodes[u].val == nodes[v].val && nodes[v].id < nodes[u].id) || nodes[u].val > nodes[v].val)swap(u, v);nodes[u].r = merge(nodes[u].r, v);if (nodes[nodes[u].r].s > nodes[nodes[u].l].s)swap(nodes[u].l, nodes[u].r);nodes[u].s = nodes[nodes[u].r].s + 1;return u;}int pre[300005];int root[300005];bool del[300005];int pop(int &u){if (u == 0)return 0;int val = nodes[u].val;del[nodes[u].id] = true;u = merge(nodes[u].l, nodes[u].r);return val;}int find(int u){return pre[u] == u ? u : pre[u] = find(pre[u]);}void unite(int u, int v){int ur = find(u);int vr = find(v);pre[ur] = vr;}int main(){int n, m;scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++){int val;scanf("%d", &val);pre[i] = i;root[i] = createNode(val);}for (int i = 1; i <= m; i++){int op;scanf("%d", &op);if (op == 1){int x;int y;scanf("%d %d", &x, &y);if (del[x] || del[y])continue;int r = merge(root[find(x)], root[find(y)]);unite(x, y);root[find(x)] = r;}else if (op == 2){int x;scanf("%d", &x);if (del[x]){printf("-1\n");continue;}int r = root[find(x)];printf("%d\n", pop(r));root[find(x)] = r;}}return 0;}

如果觉得《可并堆（左高树 左偏树）》对你有帮助，请点赞、收藏，并留下你的观点哦！