纯函数式堆（纯函数式优先级队列）part one ----二项堆
纯函数式堆（纯函数式优先级队列）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)）等内容。