左偏树(转)
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 |
#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\n" );
} 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\n" , heap[merge( u, v )].v );
}
}
}
return 0;
} |