可并堆,

左偏树学习笔记

第一篇啊第一篇啊,那个世界你好终于可以删去了诶。
左偏树感觉写的姿势不对啊,无故WA+RE(后来发现其实是并查集的问题,滚回普及去吧)


    这里是目录

左偏树的实现

一、关于左偏树

左偏树是一颗二叉树,每个节点同样只拥有最多左右两个儿子。同时它也具有堆性质。优先队列也具有这些性质但是但将两个优先队列合并时,所需的时间复杂度却是$O(nlog_2^n)$,不能快速的进行合并。而左偏树即可以$O(log_2^n)$的时间复杂度实现。

二、左偏树的性质

1、左偏树同样具有堆的性质,所以左偏树的根节点是最小的。并且每个节点的键值小于等于其左右节点的键值。即对于任意节点 $i$  有:
i->key <= i->leftson->key && i->key <= i->rightson->key

第二个性质之前,先对左偏树引入三个概念:
1、键值:可以看作该节点的大小,比如说左偏树的根节点即为键值最大(或最小)的点。
2、外节点:只有当一个节点 $i$ 满足( i->leftson == NULL || i->rightson ==NULL)时,该节点是外节点。
3、距离:点$i$的距离 = 在以 $i$ 为根的子树中,从根出发,到离$i$最近的外节点所经过的边数。

2、任意节点 $i$ 满足 i->leftson->dis >= i->rightson->dis (dis即指节点距离)。这也就是左偏树的左偏性质。
3、对于任意节点 $i$  有 i->dis = i->rightson->dis + 1

三、左偏树的定理

1、当左偏树的根节点的距离是一定值 $k$ 时,在该树是完全二叉树时,节点数最小。
证明:因为性质3,节点的距离值 $=$ 右儿子个数+1。又因为性质2,所以当且仅当 i->leftson->dis = i->rightson->dis时,节点数最小。
2、当一颗左偏树的根的距离为 $i$ 时,可以发现它的树高也为= $i$ 。 此时根据定理一即可得到,当该树节点最少时即为一颗完全二叉树。节点数 $(n)$ $>=2^{k+1}-1$ 。

四、左偏树的代码实现

对左偏树的定义:struct Tree{Tree *son[2];int dis,key;}
1、合并操作:这是左偏树各个操作的基础,几乎每个操作都会使用。
Tree *C = Merge(Tree *x,Tree *y)$\Rightarrow$ 将树 A、B合并为C 。
假设A的根比B小(否则swap(A,B)),然后则将 A 的根作为 C 的根,则 A 的左儿子不变,然后递归Merge(A->son[1],B)。在比较A->son[1]->disA->son[0]->dis[0] 的大小,否则swap(A->son[1],A->son[0])

Tree *Merge(Tree *x,Tree *y) {
    if(x==NULL) return y;
    if(y==NULL) return x;
    if(y->key > x->key) swap(x,y);
    x->son[1]=Merge(x->son[1],y);
    if(x->son[0]->dis < x->son[1]->dis) swap(x->son[0],x->son[1]);
    x->dis=x->son[1]->dis+1;
    return x;
}

2、插入操作:
Insert(int a,Tree * A) 将a插入至A中。
即可将a看作只有一个点的左偏树,然后合并即可。
Tree *Insert(int x,Tree *A) {
    Tree *B;
    B->key=x;
    B->dis=0;
    return Merge(A,B);
}

3、删除根节点:
DeleteRoot(Tree *A) 将A的根删去。
直接将A的左右儿子合并为新树即可。
Tree *DeleteMax(Tree *A) {
    return Merge(A->son[0],A->son[1]);
}

4、建树操作:
将n个数建成一个左偏树。
将这n个树分别建成只有一个节点的左偏树,然后放进一个队列。
每次从中取出两个树,Merge 后再放回,直到队列中只剩下一个树。

4 comments

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注