左偏树&斜堆

表示学这些东西是为了为学可持久化treap铺垫。

但实际上这是一种很鸡肋的数据结构。

用来解决什么问题？

就是在堆的基础上，支持O(lgn)的合并操作。

解决这个问题的似乎还有个斐波拉契堆，不懂……

数据结构核心

左偏树

struct Leftist_Tree
{
    struct Node
    {
        int l,r;
        int val,dist;
    } d[100001];
    int cnt;
    int newnode(int _val)
    {
        d[++cnt].val=_val;
        d[cnt].dist=1;
    }
    int merge(int a,int b)
    {
        if (!a)
            return b;
        if (!b)
            return a;
        if (d[a].val>d[b].val)
            swap(a,b);
        d[a].r=merge(d[a].r,b);
        if (d[d[a].r].dist>d[d[a].l].dist)
            swap(d[a].l,d[a].r);
        d[a].dist=d[d[a].r].dist+1;
        return a;
    }
}           

斜堆