左偏树

其实左偏树挺简单的。顾名思义，就是向左偏的树。至于为什么左偏，目的就是方便两个堆的合并了。

然后开始之前，学过平衡树的同学一定要牢记这是个堆，而不是排序二叉树。

定义

$\bullet$ 首先，左偏树是一个堆。

$\bullet$ 定义一个点的深度为它到距它最近的没有右子节点的节点的距离。

$\bullet$ 左子节点的深度大于等于右子节点的深度。

所以我们比较显然的可以知道，根节点的深度不超过$\lfloor \log_2(n+1)\rfloor-1$。

一个左偏树的节点，我们需要维护左子节点LeftChild、右子节点RightChild和值Value。同时由于要求堆顶，我们还需要知道$parent$信息。

相关操作

merge

设我们有两个节点数分别为$n1​$，$n2​$的小根堆，堆顶为$x​$，$y​$。现在我们需要将其合并成一个堆。我们利用上述左偏树的性质，可以得到这样的方法：

1、比较$x.Value$和$y.Value$的大小，如果$y.Value<x.Value$，则交换$x$和$y$。令$x$为新的堆顶。

2、合并$x.RightChild$和$y$，并将返回的堆顶作为$x$的新$RightChild$。

3、返回新堆顶$x$。

这样实际上就完成了合并过程。而为了保持左偏树的性质，应该在$2$之后插入如下操作：

比较$x.LeftChild$的深度和$x.RightChild$的深度，如果不满足左偏性质，就交换两颗子树。

更新$x$的深度。

不难发现，这个过程是$O(\log n)$。

insert

直接将新插入的点看做一个堆merge即可。时间复杂度$O(\log n)$

pop

删除堆顶，将两个子树merge即可。时间复杂度$O(\log n)$。

findRoot

findRoot可真是个麻烦的操作，同时也是左偏树的毒瘤之处所在。

我们发现，如果只是简单的跳parent的话，这个时间复杂度可能会被卡满，也就是$O(n)$。因为左偏树保证的深度并不是树的深度。

但是我们发现，其实我们并不需要详细的每个parent，我们只需要知道堆顶就可以了。这样是不是就可以用类似于并查集路径压缩的手段来加速了？然后findRoot的时间复杂度就被大大降低了。这样，整个左偏树的时间复杂度就得到了保证。

参考程序

题目链接

#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;

const int Maxn = 100010;
struct value {
    int Pos, Value;
    bool operator < ( const value Other ) const {
        return Value < Other.Value || Value == Other.Value && Pos < Other.Pos;
    }
    bool operator > ( const value Other ) const {
        return Value > Other.Value || Value == Other.Value && Pos > Other.Pos;
    }
};
struct node {
    value Value;
    int Father, LeftChild, RightChild, Deep, Del;
};
int N, M;
node Node[ Maxn ];

int GetFather( int x ) {
    if( Node[ x ].Father == x ) return x;
    Node[ x ].Father = GetFather( Node[ x ].Father );
    return Node[ x ].Father;
}

int Union( int x, int y ) {
    if( Node[ x ].Del && Node[ y ].Del ) return x;
    if( Node[ x ].Del ) return y;
    if( Node[ y ].Del ) return x;
    x = GetFather( x );
    y = GetFather( y );
    if( x == y ) return x;
    if( Node[ x ].Value > Node[ y ].Value ) swap( x, y );
    int Last = x; x = Node[ x ].RightChild;
    int Opt = 0;
    for( ; x && y; ) {
        if( Node[ x ].Value > Node[ y ].Value ) swap( x, y );
        Node[ Last ].RightChild = x;
        Node[ x ].Father = Last;
        Last = x;
        x = Node[ x ].RightChild;
    }
    Node[ Last ].RightChild = y;
    Node[ y ].Father = Last;
    for( ; Node[ Last ].Father != Last; Last = Node[ Last ].Father ) {
        if( Node[ Node[ Last ].LeftChild ].Deep < Node[ Node[ Last ].RightChild ].Deep )
            swap( Node[ Last ].LeftChild, Node[ Last ].RightChild );
        Node[ Last ].Deep = Node[ Node[ Last ].RightChild ].Deep + 1;
    }
    if( Node[ Node[ Last ].LeftChild ].Deep < Node[ Node[ Last ].RightChild ].Deep )
        swap( Node[ Last ].LeftChild, Node[ Last ].RightChild );
    Node[ Last ].Deep = Node[ Node[ Last ].RightChild ].Deep + 1;
    return Last;
}

void Del( int x ) {
    if( Node[ x ].Del ) {
        printf( "-1\n" );
        return;
    }
    x = GetFather( x );
    printf( "%d\n", Node[ x ].Value.Value );
    Node[ x ].Del = 1;
    Node[ Node[ x ].LeftChild ].Father = Node[ x ].LeftChild;
    Node[ Node[ x ].RightChild ].Father = Node[ x ].RightChild;
    Node[ x ].Father = Union( Node[ x ].LeftChild, Node[ x ].RightChild );
    return;
}

int main() {
    memset( Node, 0, sizeof( Node ) );
    Node[ 0 ].Del = 1;
    scanf( "%d%d", &N, &M );
    for( int i = 1; i <= N; ++i ) scanf( "%d", &Node[ i ].Value.Value );
    for( int i = 1; i <= N; ++i ) Node[ i ].Value.Pos = i;
    for( int i = 1; i <= N; ++i ) Node[ i ].Father = i, Node[ i ].Deep = 1;
    for( int i = 1; i <= M; ++i ) {
        int Opt; scanf( "%d", &Opt );
        if( Opt == 1 ) {
            int x, y; scanf( "%d%d", &x, &y );
            Union( x, y );
        }
        if( Opt == 2 ) {
            int x; scanf( "%d", &x );
            Del( x );
        }
    }
    return 0;
}