纯函数式堆(纯函数式优先级队列)part one ----二项堆
前言:
这篇文章是基于我看过的一篇论文,主要是关于函数式数据结构,函数式堆(优先级队列),
我会以自己的理解写下来,然后论文中出现的代码将会使用scala这们语言。
论文链接: Optimal Purely Functional Priority Queues,另外一个链接: 论文。
这里有个好网站介绍:coursera,全球在线课程,各种课程都有。
scala这们语言的一些学习资料:
scala的教程: scala turorials(文档和更高阶的教程这个网站上都有),
这里有一个有趣的(讲的很有趣值的一看)介绍scala的视频:
这里还有scala作者Martin Odersky在youtube上的一个视频,
主要是介绍scala这个语言是如何应对和处理并行计算所带来的挑战(youtube需*):
Martin’s talk at OSCON 2011: Working Hard to Keep it Simple。
正文:
好了,我们回到正文。
我们知道堆可用来实现优先级队列,或者说堆就是一种优先级队列。论文中的优先级队列
(priority queue),其实也就是堆(heap),反正都是差不多的东西,我还是写成堆吧。
论文中的讨论的堆支持以下4个操作:
1、findMin(h) 返回堆h中最小的元素;
2、insert(x,h) 往堆h中插入元素x;
3、meld(h1,h2) 将堆h1和h2融合成一个新堆;
4、deleteMin(h) 从堆h中删除最小的元素;
论文中首先介绍了二项堆(binomial queue),二项堆对于上述4个操作的时间复杂度是O(log n),
接着我们会用3步来优化该堆,最终的效果是,1、2、3操作的时间复杂度会变为O(1)。
第一步,引入二项堆的一个变种,斜二项堆(skew binomial queue),该堆通过消除级联链接?
(cascading links)使插入的时间复杂度为O(1);
第二步,增加一个全局root保存最小的元素,这样查找最小的元素时间复杂度变为O(1),后面会看到其实
第三步就包含了第二步,所以可以说只要两步;
第三步,通过应用一种技术data-structural bootstrapping,通过允许堆中包含另外一个堆从而使合并 (meld操作)两个堆的时间复杂度变为 O(1)。
下面会详细解释。
堆的抽象定义:
首先来看堆的抽象定义(引用自coursera的课程Principles of Reactive Programming的week 1的作业 ):
//对应论文第三页,Figure 1
trait Heap {
type H // 代表堆的类型
type A // 代表每个元素的类型
def ord: Ordering[A] // 对元素的排序方式
def empty: H // 空堆
def isEmpty( h: H ): Boolean // 判断堆h是否为空
def insert( x: A, h: H ): H // 向堆h中插入元素x
def meld( h1: H, h2: H ): H // 合并堆h1和h2
def findMin( h: H ): A // 堆h中的最小元素
def deleteMin( h: H ): H // 删除堆中的最小元素
}
//当应用到其他元素类型时,只需要类似以下定义多一个trait
trait IntHeap extends Heap {
override type A = Int
override def ord = scala.math.Ordering.Int
}
二项堆(binomial queue):
由于二项堆由二项树组成,所以我们先来看看二项树的定义。
二项树(binomial tree):
1、rank为0的二项树只有一个节点;
2、rank为r+1的二项树由两个rank为r的二项树链接而成,链接的方法是一个二项树作为另外一个二项树的
最左子树。
下面用图片举例:
以rank3的二项树为例,我们可以看到蓝色虚线框和蓝色实线框都是rank为2的二项树,其中一个
是另外一个的最左子树。然后从二项树的定义可以知道,rank为r的二项树包含2^r(2的r次方)个
节点。
二项树的另外一个等价定义:
一个rank为r的二项树相当于是一个节点,该节点有r个子节点t1 ... tr,对于ti(1 <= i <= r)
是一个rank为r - i的二项树。对照上图很容易明白。
然后假设一棵二项树是堆有序的,当该树的每个节点都比自己的子节点要小。为了保存堆顺序,
链接两棵堆有序二项树时,选择根较大的二项树作为根较小的二项树的最左子树。
然后我们回到二项堆,一个二项堆就是一个堆有序的二项树集合,该集合中每棵二项树的rank都
不一样,而且堆中的二项树以升序排列。
由于我们知道一棵rank为r的二项树 包含2^r(2的r次方)个节点,而结合二项堆的定义,我们可以
推出,一个包含n个节点的二项堆所包含的二项树就对应n的二进制表达形式中的的1。
比如:我们来看看21个节点的二项堆,由于21的二进制表达形式为:10101,所以该堆包含rank为
0、2、4 ,三棵二项树(对应的节点数分别为1、4、16,加起来就是21)。
而一个节点数为n的二项堆最多包含 [ log(n + 1) ] 棵二项树。
现在可以来描述一下二项堆的操作,因为堆中的所有二项树都是堆有序的,所以可以得出堆中的
最小元(findMin)是某棵二项树的树根。所以只要把堆中的二项树的根都遍历一遍就知道最小的元素了,
所以时间复杂度为O(log n)。对于插入一个元素(insert)的操作,首先创建一个只有一个节点的树也就是
rank为0的二项树,然后相当于向一个二进制数加一一样,如果堆中已经存在rank为0的二项树,则将这
两个二项树链接起来,然后继续将rank相同的二项树链接,相当于加一之后的进位,如果没有rank为0的
二项树,则直接将该节点放到二项树列表的头部。最差的时间复杂度为 O(log n),即是一个节点数为n的
二项堆,n = 2^k - 1,相当于二进制位全部为一,这时加一会导致k次进位,也就是要做k次链接,
这也是后面要讲到的斜二项堆会优化的方面,通过消除这种情况,使插入的时间复杂度为O(1)。
容易推出,合并(meld)两个二项堆就相当于两个二进制数相加,升序遍历两个堆的树然后将rank
相同的树链接在一起,一次链接就相当于一次进位,时间复杂度也是(log n)。
最后到deleteMin操作,首先遍历堆中的树根,找到根最小的二项树,然后删除该节点,返回该树
的子树,由于子树是以降序排列的,所以要反转顺序,然后该被删除的树的子树也组成一个二项堆,
于是剩下的操作就是将该堆和原来的堆合并,找树和合并都需要O(log n)的时间,所以总共需要
O(log n)的时间复杂度。
上图解释插入操作:
这个图解释了插入操作的过程,还有上面的说到的,k次链接问题(当n=2^k-1)。
合并两个堆和删除最小的情况参照上图读者自己能画出来。
二项堆的定义:
二项堆的定义(引用自coursera的课程Principles of Reactive Programming的week 1的作业 ):
// 对应论文Figure 3, 第七页 7
trait BinomialHeap extends Heap {
type Rank = Int
case class Node( x: A, r: Rank, c: List[Node] ) //定义节点,也就是二项树
override type H = List[Node] //堆的定义,是由二项树组成的列表
protected def root( t: Node ) = t.x //取得树根的值
protected def rank( t: Node ) = t.r //取得树的rank
//链接两棵rank相同的树,树根值大的元素作为树根值小的元素的最左子树
protected def link( t1: Node, t2: Node ): Node = // t1.r==t2.r
if ( ord.lteq( t1.x, t2.x ) )
Node( t1.x, t1.r + 1, t2 :: t1.c )
else
Node( t2.x, t2.r + 1, t1 :: t2.c )
//往堆中插入一棵树
protected def ins( t: Node, ts: H ): H = ts match {
case Nil => List(t) //若堆为空,直接返回只有一棵树的堆
case tp :: ts => //其实认真想一下只有t.r <= tp.r的情况出现,所以如果t.r不小于tp.r,
//则t.r == tp.r,所以将之链接起来,然后插入到堆ts中
if ( t.r < tp.r ) t :: tp :: ts else ins( link( t, tp ), ts )
}
override def empty = Nil //空堆
override def isEmpty(ts: H) = ts.isEmpty //判断堆是否为空
//往堆中插入一个元素,insert函数和ins函数有点令人困惑,论文中说了,这几乎是
//所有的二项树实现都有的问题
override def insert( x: A, ts: H ) = ins( Node( x, 0, Nil ), ts )
//合并两棵树
override def meld( ts1: H, ts2: H ) = ( ts1, ts2 ) match {
case ( Nil, ts ) => ts
case ( ts, Nil ) => ts
case ( t1 :: ts1, t2 :: ts2 ) =>
if ( t1.r < t2.r ) t1 :: meld( ts1, t2 :: ts2 ) //二进制数相加一样
else if ( t2.r < t1.r ) t2 :: meld( t1 :: ts1, ts2 )
else ins( link( t1, t2 ), meld( ts1, ts2 ) )
//当找到两个rank相同的树,则先链接两棵树,然后
//将链接后得到的树插入到剩下已经合并的堆中。
}
//找最小元素
override def findMin( ts: H ) = ts match {
case Nil => throw new NoSuchElementException( "min of empty heap" )
case t :: Nil => root(t)
case t :: ts =>
val x = findMin(ts)
if ( ord.lteq( root(t), x ) ) root(t) else x
}
//删除最小元素
override def deleteMin( ts: H ) = ts match {
case Nil => throw new NoSuchElementException( "delete min of empty heap" )
case t :: ts =>
def getMin( t: Node, ts: H ): ( Node, H ) = ts match {
//辅助函数,找到堆中最小的树,返回值
case Nil => ( t, Nil ) //Node代表根最小的树,H是已经删除Node
case tp :: tsp => //的堆,虽然是递归看的有点头晕,但其实就是
//从列表的最后一棵树开始遍历到头,相邻两
//棵树互相比较,每次比较最小的树就是tq
//最后回溯到头就找到根最小的树了
val ( tq, tsq ) = getMin( tp, tsp )
if ( ord.lteq( root(t), root(tq) ) ) (t, ts)
else ( tq, t :: tsq )
}
val ( Node( _, _, c ), tsq ) = getMin( t, ts )
meld( c.reverse, tsq ) //将被删除节点的子树和剩下的树合并
}
}
好,二项树就介绍完了,part two的内容是介绍斜二项堆,斜二项树(解决k次链接,使得插入操作的时间复杂度
为O(log n))等内容。
转载于:https://my.oschina.net/Ldpe2G/blog/184278