[关闭]
@xzyxzy 2018-04-01T08:56:13.000000Z 字数 1572 阅读 663

左偏树

数据结构

更好阅读体验: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)但常数小

二、题目

三、难点

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

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

  1. int Merge(int x,int y)
  2. {
  3. if(!x||!y)return x+y;
  4. if(t[x].val<t[y].val)swap(x,y);
  5. rc=Merge(rc,y);
  6. fa[rc]=x;//这一句
  7. if(t[lc].dis<t[rc].dis)swap(lc,rc);
  8. t[x].dis=t[rc].dis+1;
  9. return x;
  10. }
  11. int Delete(int x)
  12. {
  13. fa[lc]=lc;fa[rc]=rc;//为了记录节点所在堆的堆顶编号,这里需要有所改动
  14. return fa[x]=Merge(lc,rc);
  15. }

难点2

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

四、比较

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

Part 1 效率比较

题目 方式 时间 内存 web
Monkey King 左偏树 108ms 4093KB 提交状态
启发式合并 296ms 10257KB 提交状态
崎岖的山路 左偏树 52ms 7542KB 提交状态
启发式合并 680ms 11097KB 提交状态
左偏树模板 左偏树 72ms 4464KB 提交状态
启发式合并 104ms 10078KB 提交状态
[APIO2012]派遣 左偏树 284ms 12621KB 提交状态
启发式合并 520ms 21437KB 提交状态
逃跑的... 左偏树 416ms 18964KB 提交状态
启发式合并 680ms 29992KB 提交状态
棘手的操作 左偏树 864ms 13917KB 提交状态
启发式合并 卡不过去 \ 提交状态

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

Part 2 代码难度比较

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

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

注意结构题排序:

  1. struct food
  2. {
  3. int id,tim;
  4. bool operator < (const food &b)const
  5. {
  6. return tim>b.tim;
  7. }
  8. //表示按tim从小到大排序(不清楚可以试试,注意const)
  9. };

Part 3 功能比较

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

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

打懒标记

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

从堆中取出指定元素

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注