几种初级二叉可并堆简介

· · 个人记录

前言

我问过一些男性OIer，女生的哪些习惯会让你厌恶？

有人说：不温柔。

有人说：分块时不解均值不等式，默认块的大小为\sqrt{n}。

有人说：写Treap、模拟退火时用系统默认随机数种子。

有人说：利用CRT解一元模线性方程组时忽略不互质的情况直接套用公式。

还有人说：偷懒使用斜堆代替左偏树。

emm……斜堆，左偏树……

前置知识：对洛谷日报第11期中的二叉堆完全理解，且可以完全实现。

一、可并堆

一般的二叉堆支持完成以下操作：

这样的二叉堆想必大家早已经能熟练地用std::priority_queue水过了。

可并堆还要求在\log n的时间内完成两个堆的合并。原来的二叉堆要想完成这一操作，时间复杂度为n\log n，使用启发式合并的话，比我们想要的复杂度足足多了一个\log，这是不清真的。

为了实现这一操作，我们可以使用斜堆、左偏树、随机堆、配对堆、二项堆或斐波那契堆再或者pb_ds中的各种优先队列。

这里讲三种容易理解，容易实现的可并堆。

二、斜堆

1、斜堆的整体结构

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

原来我们写过的二叉堆是一棵完全二叉树，但斜堆不是。斜堆甚至不必保证平衡，每个结点的左右儿子的大小关系也没有任何规定。

对于每个节点，我们这样描述：

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

也就是记录自己的值和左右儿子。

2、push和merge

我们可以把单独的一个节点也看成是一个斜堆，这样可以统一为merge操作。

一开始我们可能会想到这样的搞法：选择a和b两个斜堆中根节点键值较小的一个，让它的右子树与另一棵树递归合并下去，再把合并出的东西当做新的右子树。

但是这样下去，右子树会很dark♂，左子树却很小，斜堆变得不平衡。

我们可以再加一步操作，插入完就交换左右儿子。这样，在一次次的合并后，这个斜堆就较为平衡了。

以上操作也可以换成插入到左子树。

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]=join(node[root1].ch[1],root2);
    std::swap(node[root1].ch[0],node[root2].ch[1]);
    return root1;
}

3、pop

删除根节点，合并根节点的两个子树即可。

4、时间复杂度分析

最坏情况下，斜堆可以被精心构造的毒瘤数据卡成一条链，时间复杂度O(n)。然而，在绝大多数情况下，均摊时间复杂度是O(\log n)，有人证明，其均摊复杂度最坏不超过O(4\log n)。

同时，有这样一个问题，如果合并后的左子树仍远大于右子树，交换后再进行后续合并不就更偏了吗？

二、左偏树

1、左偏树的结构与性质

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

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

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

2、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;
}

3、pop

参考斜堆。

4、时间复杂度分析

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

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

三、随机堆

1、随机堆的结构

参见斜堆。

2、push和merge

push视为merge。

为了减小常数与略微减少代码量，我们必须舍弃左偏树的交换与维护。但是又不能像斜堆那样被卡成一条链。也就是说，我们要往两边都均匀插入。怎么办呢？

随机数了解一下！

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

这玩意甚至不需要交换左右儿子！而且毒瘤出题人没法卡它！

3、pop

参考斜堆。

4、时间复杂度分析

合并操作最坏O(n)，均摊O(\log n)。常数小，代码复杂度小（说得好像左偏树代码复杂似的），可以完全替代左偏树。

四、总结

以后不需要偷懒用斜堆代替左偏树了，我们可以洗把脸然后用随机堆。当然pb_ds也是很好的选择。

留三道练习题：

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

这道题的并查集不能路径压缩。

P1456 Monkey King

这道题是简单题。

P3261 JLOI2015 城池攻占

这道题不止可并堆这一种做法，但是可并堆的代码复杂度最低。

（逃