<总结>左偏树

还是不把数据结构的总结文章的标题用\<算法>这种名字了......

维基百科英文版的,这里的内容很多参考了那边:这里
(啊那个中文版太扯了)

左偏树满足堆结构,特点:可合并。声明:可并堆不止左偏树。
左偏树名字的由来:左偏树的左子树通常比右子树高。

定义左偏树中,一个节点的 s值(s-value)排名(rank) 为其离最近的一个叶子节点的距离。所有包含空儿子的节点的s值隐式定义为0(在某些描述中,空节点的s值被假定为-1)。

左偏树不仅有BST的性质,并且每个节点的左儿子的s值大于右儿子的s值(如果有)。

合并:
合并操作以两棵左偏树作为输入,并返回一棵左偏树,其中包含两棵原始左偏树中的所有节点。如果两棵左偏树中的一棵为空,则合并操作返回另一棵非空的左偏树。

  1. 我们假设原始左偏树的根分别为A和B,其中v_A \ge v_B(例子为小根堆)。否则,我们可以交换A和B,使上述条件成立;
  2. 将B与A的右子树合并;
  3. 因为上一次操作可能会改变A的右子树的s值。为了维护左偏树属性,在每次B与A的右子树合并并且A的右子树被修改完成后,我们还应检查右子树的s值是否大于左子树的s值,如果右子树的s值大于左子树的s值,我们就交换左右子树。
  4. 如果这个节点只有一个子节点,那么这个子节点应该是左儿子
Node *merge(Node *x, Node *y)
{
    if (x == 0) return y;
    if (y == 0) return x;
    if (x->v > y->v || (x->v == y->v && x > y)) std::swap(x, y);
    //啊,或右边的表达式是洛谷板子的要求:当堆里有多个最小值时,优先删除原序列的靠前的
    x->r = merge(x->r, y);
    x->r->f = x;//方便找root
    if ((x->l ? x->l->d : -1) < x->r->d) std::swap(x->l, x->r);
    x->d = (x->r) ? (x->r->d + 1) : 1;
    return x;
}

这样合并就好了
然后删除堆顶的话,我们只需要把堆顶左右子节点合并即可。

然后你发现你这么写了,然后T了一个点
为什么呢?那是因为小粉兔出了数据卡了我们找堆顶的方式:

Node *get(Node *p)
{
    if (p->f) p = p->f;
    return p;
}

因为最坏情况下,树高n,那么这个get就会很气。
怎么办呢,路径压缩...

我们让每个点尽量指向离根近一点的点(或者就是根)...然而这不代表左偏树就不是二叉树了,因为我们的fa只是找root的罢了...

最终函数

Node *get(Node *p)
{
    if (p->f != p) return p->f = get(p->f);
    return p;
}

//main()
for (int i = 1; i <= n; ++i)
    scanf("%d", &nd[i].v), nd[i].f = nd + i;//fa[i] = i

//main():merge
Node *a = get(nd + x), *b = get(nd + y);
if (a==b)
    continue;
a->f = b->f = merge(a, b);

//main():pop
ro = find(nd + x);
ro->v = 0;
ro->f = merge(ro->l, ro->r);//这里!
if (ro->l)
    ro->l->f = ro->f;
if (ro->r)
    ro->r->f = ro->f;

注意我们的删除!删除的点我们还是让它的fa指向堆的根,因为可能有其他的节点指向它,它不能直接去世。

啊对了口胡一个删点
当然你要知道这个节点的编号,要不然emm
先把这个点val置无效值,然后合并这个点的左右子节点,最后沿着fa向上跳检查左偏树性质

啊对了再口胡一个建堆(放心放心,维基上面的):
使用队列来存储每个节点和结果树。每次取队列头两项,合并这两棵树并重新放置到队列尾部中。这可以在O(n)时间内初始化左偏树。

是不是很短啊?我们来了解一下时间复杂度:

操作 时间复杂度
建树(朴素) O(n\log n)
建树 O(n)
(已知堆顶)最值查询 O(1)
删根 O(\log n)
删点(已知节点编号) O(\log n)
合并 O\log n

最后扯一下,中英文维基百科的左偏树:(还可以注意一下右边的滚动条)
酱
百度百科嘛emm反正都是抄的维基

点赞

发表评论

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