左偏树（转）

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

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

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

[性质1] 节点的键值小于或等于它的左右子节点的键值。

[性质2] 节点的左子节点的距离不小于右子节点的距离。

[性质3] 节点的左子节点右子节点也是一颗左偏树。

合并操作的代码如下：

Function Merge(A, B)
    If A = NULL Then return B
    If B = NULL Then return A
    If key(B) < key(A) Then swap(A, B)
    right(A) ← Merge(right(A), B)
    If dist(right(A)) > dist(left(A)) Then
        swap(left(A), right(A))
    If right(A) = NULL Then dist(A) ← 0
    Else dist(A) ← dist(right(A)) + 1
    return A
End Function

hdoj 1512 Monkey King

#include <iostream>
#include <vector>
using namespace std;
 
const int maxn = 100005;
 
 
struct tree {
    int l, r, v, dis, f;
}heap[maxn];
 
 
int merge( int a, int b ) {
    if( a == 0 ) return b;
    if( b == 0 ) return a;
    if( heap[a].v < heap[b].v ) swap( a, b );
    heap[a].r = merge( heap[a].r, b );
    heap[heap[a].r].f = a;
    if( heap[heap[a].l].dis < heap[heap[a].r].dis ) swap( heap[a].l, heap[a].r );
    if( heap[a].r == 0 ) heap[a].dis = 0;
    else heap[a].dis = heap[heap[a].r].dis + 1;
    return a;
}
 
 
int pop( int a ) {
    int l = heap[a].l;
    int r = heap[a].r;
    heap[l].f = l;
    heap[r].f = r;
    heap[a].l = heap[a].r = heap[a].dis = 0;
    return merge(l, r);
}
 
 
int find( int a ) { return heap[a].f == a ? a : find( heap[a].f ) ; }
 
void Read( int &x ) {
    char ch;
    x = 0;
    ch = getchar();
    while( !(ch >= '0' && ch <= '9') ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) {
        x = x * 10 + ch - '0' ;
        ch = getchar();
    }
}
 
     
int main() {
//  freopen( "c:/aaa.txt", "r", stdin );
    int i, a, b, finda, findb, n, m;
    while( scanf( "%d", &n ) == 1 ) {
        for( i=1; i<=n; ++i ) {
            Read(heap[i].v);
            //scanf( "%d", &st[i].v );
            heap[i].l = heap[i].r = heap[i].dis = 0;
            heap[i].f = i;
        }
         
        //scanf( "%d", &m );
        Read( m );
        while( m-- ) {
            //scanf( "%d %d", &a, &b );
            Read( a ); Read( b );
            finda = find( a );
            findb = find( b );
            if( finda == findb ) {
                printf("-1
");
            } else {
                heap[finda].v /= 2;
                int u = pop( finda );
                u = merge( u, finda );
 
                heap[findb].v /= 2;
                int v = pop( findb );
                v = merge( v, findb );
 
                printf( "%d
", heap[merge( u, v )].v );
            }
        }   
    }
    return 0;
}