左偏树

数据结构

更好阅读体验：https://www.zybuluo.com/xzyxzy/note/1052226

一、概述

引用：
ZSY：http://www.cnblogs.com/zhoushuyu/p/8169074.html
DWQ：http://www.cnblogs.com/sdzwyq/p/8460195.html

就是可并堆的一种，和启发式合并复杂度一样（nlogn）但常数小

二、题目

• [2018.2.23]崎岖的山路(road)
• [Luogu]模板左偏树(可并堆)
• [Luogu]Monkey King
• [USACO12DEC]逃跑的BarnRunning Away From…
• [JLOI2015]城池攻占
• [APIO2012]派遣
• [HDU]Joint Stacks
• [HDU]To Be Or Not To Be
• [SCOI2011]棘手的操作

三、难点

难点1：记录点所在的堆的编号

这是最常用的，比如合并$x$和$y$所在的堆，这时候就要用到并查集了
具体来说，脑袋保持高度清醒，数组下标表示的是堆的编号还是点的编号一定要策清楚
这样大概就没有问题了，顺着思路可以写下去
PS：这样写常数巨小（冲榜助力）

int Merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(t[x].val<t[y].val)swap(x,y);
    rc=Merge(rc,y);
    fa[rc]=x;//这一句
    if(t[lc].dis<t[rc].dis)swap(lc,rc);
    t[x].dis=t[rc].dis+1;
    return x;
}
int Delete(int x)
{
    fa[lc]=lc;fa[rc]=rc;//为了记录节点所在堆的堆顶编号，这里需要有所改动
    return fa[x]=Merge(lc,rc);
}

难点2

左偏树是可以打懒标记的
具体自己YY吧，不难
例题：城池攻占/棘手的操作

四、比较

优先队列的启发式合并在一定程度上是可以和左偏树相互替代的
但是通过众多实例，左偏树效率略高（每道题用两种方法真是累死我了）

Part 1 效率比较

显然左偏树更胜一筹，在时间和空间上都要优秀些

Part 2 代码难度比较

代码难度是差不多的，但是经过一段时间没有码左偏树，那么模板就会忘得差不多了，然而启发式合并的思想是十分简单的，就算很久没有打自己也可以很轻松地摸索出来

显然启发式合并在记忆方面略有优势

注意结构题排序：

struct food
{
    int id,tim; 
    bool operator <  (const food &b)const
        {
            return tim>b.tim;
        }   
    //表示按tim从小到大排序（不清楚可以试试，注意const）
};

Part 3 功能比较

在上表格的题中，所有左偏树能实现的功能优先队列都可以实现
具体有

• 堆的合并
• 好像没了诶。

嗯好的然后左偏树还有一些功能用优先队列是不能实现的
在之前总是傻傻地认为两个东西可以完全等价看来是做题不够
左偏树还可以

打懒标记

真的什么懒标记都可以打，乘的加的异或的，优先队列(合并的时候)就做不到了

从堆中取出指定元素

这个真的厉害啦，操作是把左右儿子合并接到原来的父亲上，注意判断该点为叶子节点的情况，例题见棘手的操作