参考：bilibili

可并堆

优先队列的缺点：无法高效合并两个堆

左偏树

节点中的数字是它的键值，而它是个堆，因此它满足堆的性质：节点的键值小于左右子节点的键值

节点外蓝色数字叫做该节点的距离

• 距离的定义：离该节点最近的“外节点”到该节点的距离
• 外节点：左右儿子不完整的节点

左偏树保证节点的左儿子的距离不小于右儿子的距离

因此可以推出一个节点距离等于右子节点的距离+1

所以空节点的距离为-1

另外，一个N节点的左偏树根节点的距离最大为 (log (N+1) -1)

性质总结

1. 小根性质：节点键值小于等于左右儿子的键值
2. 左偏性质：节点左儿子的距离不小于其右儿子的距离
3. 节点的距离等于其右儿子的距离+1

合并

合并过程中，要维护好左偏树的性质，只要合并后的堆依然满足性质，就合并成功

具体步骤

1. 设要合并的两个堆的堆顶节点为 x, y，且 (val_x le val_y)
2. 因为小根性质，合并好后的堆的堆顶一定还是 x，所以我们递归合并 x 的儿子（左右都行，一般用右）和 y
3. 因为合并完成后可能破坏 x 的左偏性质，所以如果 x 不满足左偏性质了，就交换 x 的左右儿子
4. x 的距离有可能变化，利用性质三，令 (dist_x) 等于其右儿子的距离 +1

push 与 pop

• push：

和 fhq treap 一样，新建节点然后合并即可

• pop：

合并堆顶节点的两儿子作为新堆顶即可

另外可以把节点的值设为 -1 来标记这个节点被删除了

所以原堆顶的值被设置为 -1 来标记其被删除了

模板题——P3377

• 节点

struct node
{
    int l, r, fa;
    int val, dis;
}t[N];

• 初始化

t[0].dis = -1;
for(int i = 1; i <= n; i ++ )
{
    t[i].val = read();
    t[i].fa = i;
}

• 合并

int merge(int x, int y)
{
    if(!x || !y) return x + y;
    //||前维护小根堆, ||后是题目要求值相同的下标小的优先级高
    if(t[x].val > t[y].val || (t[x].val == t[y].val && x > y))
        swap(x, y);
    
    t[x].r = merge(t[x].r, y);
    t[t[x].r].fa = x;
    if(t[t[x].l].dis < t[t[x].r].dis)
        swap(t[x].l, t[x].r);
    
    t[x].dis = t[t[x].r].dis + 1;
    return x;
}

• 并查集

int find(int x)
{
    if(t[x].fa != x) t[x].fa = find(t[x].fa);
    return t[x].fa;
}

• 删除堆顶

inline void pop(int x)
{
    t[x].val = -1;
    t[t[x].l].fa = t[x].l;
    t[t[x].r].fa = t[x].r;
    t[x].fa = merge(t[x].l, t[x].r);
}

• 完整代码

#define LOCAL
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int N = 1e5 + 10;
struct node
{
    int l, r, fa;
    int dis, val;
}t[N];

int merge(int x, int y)
{
    if(!x || !y) return x + y;

    if(t[x].val > t[y].val || (t[x].val == t[y].val && x > y))
        swap(x, y);
    
    t[x].r = merge(t[x].r, y);
    t[t[x].r].fa = x;
    if(t[t[x].l].dis < t[t[x].r].dis)
        swap(t[x].l, t[x].r);
    
    t[x].dis = t[t[x].r].dis + 1;
    return x;
}

inline void pop(int x)
{
    t[x].val = -1;
    t[t[x].l].fa = t[x].l;
    t[t[x].r].fa = t[x].r;
    t[x].fa = merge(t[x].l, t[x].r);
}

int find(int x)
{
    if(t[x].fa != x) t[x].fa = find(t[x].fa);
    return t[x].fa;
}

int n, m;

int main()
{
    #ifdef LOCAL
        freopen("D:\workspace\in_and_out\in.in", "r", stdin);
        freopen("D:\workspace\in_and_out\out.out", "w", stdout);
    #endif

    n = read(), m = read();
    t[0].dis = -1;

    for(int i = 1; i <= n; i ++ )
    {
        t[i].val = read();
        t[i].fa = i;
    }

    while(m -- )
    {
        int op = read(), x = read();
        if(op == 1)
        {
            int y = read();
            if(t[x].val == -1 || t[y].val == -1) continue;

            int pa = find(x), pb = find(y);
            if(pa == pb) continue;
            t[pa].fa = t[pb].fa = merge(pa, pb);
        }
        else
        {
            if(t[x].val == -1) puts("-1");
            else 
            {
                cout << t[find(x)].val << endl;
                pop(find(x));
            }
        }
    }
    
    return 0;
}