注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

1行可并堆,就选Random Heap  

2010-07-30 11:53:38|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最近在做poj3016K-Monotonic
先说说这题怎么做吧。参见Baltic OI 2004 sequence
自己去看就行了。这题就是跑2*N遍sequence,当然了,要先把严格”上升“转化为”不降“。

关键是可并堆的实现。论文中介绍了一个叫”左偏树“的东西,很好很优秀。不过,写起来稍微有点麻烦(至少7行!)
我本着”短代码就是生产力“的思想,希望能够开发一个超级好写的可并堆。怎么办呢?
首先,分析一下左偏树的本质。我们知道,任何一个用二叉树实现的堆(父亲大于儿子的那种),
都是可以合并的,只不过会打乱原来的某些性质(例如二叉堆,合并之后就不是完全二叉树了)
方法如下:
Merge(p,q)
   如果p或q之一是空的(null) return p+q
   if (p中的最小元素(就是他的根)比q中的最小元素大) 交换p,q
   p->左子树  =   Merge(p->左子树,q)        ///**************
   return p
请注意,带*号的那行中左子树是可以替换为右子树的。
这时,我们很纠结:带*的那一行,到底是选左子树和q合并,还是右子树呢?
这两种策略都有可能导致merge的过程花费很差很长的时间。
所谓左偏树,就用了一种启发式的方法来处理这个问题:
让q和p的”距离“短的那个子树合并!而所谓”距离“的定义,就是从这个节点Merge下去可能的最长路径的长度。

如果说左偏树是可并堆中的avl,那么”斜堆“就是可并堆中的splay:每次合并之后,都把左右子交换一下,用均摊分析来保证复杂度。
好了,那有没有可并堆中的treap?
当然!我们有了一个大胆的创意:每次随机和左子树或右子树合并!这就形成了一个随机化的堆:Random Heap
具体实现嘛,就一行,不过有点长,这一行有89个字符
node *M(node *p,node *q){
return (!p||!q)?(p?p:q):(p->k<q->k?M(q,p):((ran()?p->r=M(p->r,q):p->l=M(p->l,q)),p));//就是这一行
}
数据结构的定义如下:
struct node{node *l,*r;int k;};
还有一个我自己写的随机生成器:
int ran(){static int x=1;x+=(x<<2)+1; x&=(0x7fffffff);return x&(65536);}
所谓插入,就是合并:x=Merge(x,y);
所谓弹出最小,就是合并:x=Merge(x->l,x->r);
有人一听”左偏树“就头疼,其实,"可并堆”不只"左偏树"一个!还有斐波那契堆(更头疼)和随机heap!
就89个字符,就1行,随机heap就是如此简单。
那效率如何?
经过我测试,在poj3016上,随机heap和左偏树跑的时间没有太大差别,只慢一点点(总时间慢6.7%)。
哈哈,曾经不敢触及的“可并堆”在随机化的作用下,变得如此轻松+愉快。

附:我这题的代码:http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/3016.cpp
附:左偏树的代码:(其实也没多长,可谁让我懒呢?)
struct node{
node *l,*r;
int d,k;
node(){l=r=NULL;}
};
#define DIST(_) (_?_->d:-1)
#define SWAP(_,__) t=_,_=__,__=
node *Merge(node *p,node *q){
static node *t; if (!p || !q)return p?p:q; 
if (p->k<q->k)SWAP(p,q);
p->r=Merge(p->r,q); 
if (DIST(p->l)<DIST(p->r))SWAP(p->l,p->r);
return p->d=DIST(p->r)+1,p; 
}
  评论这张
 
阅读(2412)| 评论(7)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017