可并堆之左偏树总结

mrh929

6 年前

可并堆之左偏树总结

左偏树，顾名思义，是左边的结点权值较大的树形数据结构。主要用于两个优先队列的快速合并，是可并堆的一种实现方式。

定义与性质：

外结点：一个结点的右子结点为空就为外结点
距离：结点一直向右，直到外结点所经历的步数，每个结点距离等于右儿子的距离+1。
左偏树的父亲结点的优先级高于儿子结点
父亲结点的左子节点的距离大于等于右子节点的距离

合并操作：

大体流程：递归操作，将b结点与a结点的右孩子合并，同时会将b结点的左右孩子合并……以此类推，然后根据实际情况维护左孩子与右孩子的位置顺序

伪代码：

merge(a,b)//a与b都是小顶堆
{
- If(a==null) return b;//a为空，根节点为b
- If(b==null) return a;//b为空，根节点为a
- If(key(a)>key(b)) swap(a,b);//将优先级高树的放在左边，左右子树调换位置
- a.rchild=Merge(a.rchild,b);//a作为根，a的右孩子和b作为孩子递归
- If(dis[a.rchild]>dis[a.lchild]) swap(a.lchild,a.rchild);//a的孩子节点排序
- dis[a]=dis[a.rchild]+1;//a的距离更新
- return a;//返回根节点
}

插入操作：将新结点当作只有一个根的左偏树，merge合并。

删除操作：直接删除根结点，合并左右子树。

1636:猴王

时间限制:1 Sec 内存限制:128 MB
提交:32 解决:6
[提交][状态][讨论版]

题目描述

很久很久以前，在一个广阔的森林里，住着n只好斗的猴子。起初，它们各干各的，互相之间也不了解。但是这并不能避免猴子们之间的争吵，当然，这只存在于两个陌生猴子之间。当两只猴子争论时，它们都会请自己最强壮的朋友来代表自己进行决斗。显然，决斗之后，这两只猴子以及它们的朋友就互相了解了，这些猴子之间将再也不会发生争论了，即使它们曾经发生过冲突。
假设每一只猴子都有一个强壮值，每次决斗后都会减少一半(比如10会变成5，5会变成2.5)。并且我们假设每只猴子都很了解自己。就是说，当它属于所有朋友中最强壮的一个时，它自己会站出来，走向决斗场。

输入

输入分为两部分。
第一部分，第一行有一个整数n(n<=100000)，代表猴子总数。
接下来的n行，每行一个数表示每只猴子的强壮值(小于等于32768)。
第二部分，第一行有一个整数m(m<=100000)，表示有m次冲突会发生。
接下来的m行，每行包含两个数x和y，代表第x个猴子和第y个猴子之间发生冲突。

输出

输出每次决斗后在它们所有朋友中的最大强壮值。数据保证所有猴子决斗前彼此不认识。

样例输入

2 3

3 4

3 5

1 5

样例输出

很经典的左偏树题，每次两只猴子打架之后将两只猴子所属的堆合并起来，并且将最强壮的猴子置于堆顶

#include
#include
#include
using namespace std;
const int MAX=1000000;
int lch[MAX],rch[MAX],father[MAX],dis[MAX],data[MAX];
int n,m;
bool cmp(int a,int b){
    return a>b;
}

int Merge(int a,int b){
    if(a==0) return b;
    if(b==0) return a;
    if(!cmp(data[a],data[b])) swap(a,b);
    rch[a]=Merge(rch[a],b);
    father[rch[a]]=a;//记录父亲 
    if(dis[rch[a]]>dis[lch[a]]) swap(lch[a],rch[a]);//a的距离必须大于b 
    dis[a]=dis[rch[a]]+1;//a的距离更新 
    return a;
}

int Getfather(int p){
    if(father[p]==p) return p;
    father[p]=Getfather(father[p]);
    return father[p];
}

void Fight(int a,int b){//这里将aa bb先删除,再与他们儿子合并后的树合并，再将两个堆合并，使左偏树符合堆的性质 
    int temp,xroot,yroot,aa,bb;
    aa=Getfather(a); bb=Getfather(b);//找到战斗力最强的猴子aa,bb 
    data[aa]>>=1; data[bb]>>=1;//战斗力减少一半 
    temp=Merge(lch[aa],rch[aa]);//合并aa猴子的后代 
    lch[aa]=rch[aa]=0;
    xroot=Merge(aa,temp);//aa猴子与aa猴子后代合并 
    temp=Merge(lch[bb],rch[bb]);//合并bb猴子 的后代 
    lch[bb]=rch[bb]=0;
    yroot=Merge(bb,temp);//bb猴子与bb猴子后代合并
    temp=Merge(xroot,yroot);//合并得到当前最强壮的猴子 
    father[a]=father[b]=father[aa]=father[bb]=father[xroot]=father[yroot]=temp;
    printf("%d\n",data[temp]);
}

int main(){
//   freopen("in.txt","r",stdin);
    int a,b;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&data[i]);
    for(int i=1;i<=n;i++)
        father[i]=i;
    scanf("%d",&m);
    
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        Fight(a,b);
    }
    
    return 0;
}