常用二叉可并堆——左偏树

· · 个人记录

要求：了解什么是左偏树。不必熟练掌握左偏树的写法。

一、左偏树的结构与性质

左偏树也是一棵二叉树，也满足堆的性质。以小根堆为例，每个非根结点的值都比它父亲大。因此在整棵左偏树中，根的值最小。

即左偏树的性质一（以小根堆为例）：

val_p\leq val_{lson} val_p\leq val_{rson}

左偏树的每个节点记录四个值：左儿子，右儿子，权值和距离。

struct Node
{
    int ch[2],val,height;
}

所谓距离，是指一个节点到其子树内最近叶节点的距离。叶节点的距离是0。

为了体现名字中的“左偏”，我们钦定每个节点左儿子的距离大于等于右儿子的距离。整个树就是一种左边重右边轻的状态。

即左偏树性质二：

height_{lson}\leq height_{rson}

所以，距离父节点最近的叶节点一定在右子树中，可得左偏树性质三：

height_p=height_{rson}+1

节点数一定的情况下，要使根节点的距离最大，就要让这棵树形成完全二叉树。这样可以使得离根节点最近的叶节点尽可能远。

设此时height_{root}=k，则有节点数n=2^{k+1}-1。即得所有情况下n\geq 2^{k+1}-1。易见左偏树性质四：

height_{root}\leq \log^{n+1}_2-1

二、push和merge

同样地，把push视为merge来处理。

当我们要合并两棵左偏树a和b时，不妨设val_{roota}<val_{rootb}。大部分操作和斜堆相同，不同的是要保证左偏性质，还要维护节点的距离。那么只需在合并后检查两个儿子的距离大小关系，当左儿子距离小于右儿子时交换即可。在返回新得到的树根前，修改根节点的距离，使其满足性质三。

合并前

合并后

int merge(int root1,int root2)
{
    if(!root1||!root2)
        return root1+root2;
    if(node[root1].val>node[root2].val)
        std::swap(root1,root2);
    node[root1].ch[1]=merge(node[root1].ch[1],root2);
    if(node[node[root1].ch[0]].height>node[node[root1].ch[1]].height)
        std::swap(node[root1].ch[0],node[root1].ch[1]);
    node[root1].height=node[node[root1].ch[1]].height+1;
    return root1;
}

三、pop

参考斜堆。

四、时间复杂度分析

左偏树的左偏性保证了它不会退化成链，保证了它最坏情况下的效率。由于两棵被合并的左偏树a和b的根节点距离分别不大于\log^{size_a+1}_2-1和\log^{size_b+1}_2-1，合并的复杂度为\log^{n^2}_2。

然而可以从我写的很丑的代码看出，左偏树的常数并不小，在实际应用中，面对随机数据，反而比斜堆要慢。

五、例题

P3377 【模板】左偏树（可并堆）

P3261 JLOI2015 城池攻占