纯函数式堆（纯函数式优先级队列）part two ----斜二项堆
纯函数式堆（纯函数式优先级队列）part two ----斜二项堆
前言：
这篇文章是基于我看过的一篇论文，主要是关于函数式数据结构，函数式堆（优先级队列），
我会以自己的理解写下来，然后论文中出现的代码将会使用scala这们语言。
论文链接： Optimal Purely Functional Priority Queues，另外一个链接： 论文。
正文：
紧接part one的内容，接下来进入斜二项堆。
斜二项堆（skew binomial queue）：
斜二项堆支持插入操作O(1)的时间复杂度，通过借用random-access lists中的技术来消除上述的连续
进位问题。
为了解决这个问题，我们先来了解斜二进制数（Skew binary number），斜二进制最多只有一次进位。
斜二进制数（Skew binary number）：
同二进制不同的地方在于，斜二进制数第k个数字代表2^(k+1) - 1（2的k+1次方减一），而不是
二进制的2^k。每个位上的数字是0或者1，而二进制不同的是，最低非零位可以为2。
下面是二进制与斜二进制对应的位置的权值对比：
从最低为开始： 0 1 2 3 4 5 6 7 8 .....
斜二进制： 1 3 7 15 31 63 127 255 1023 .....
二进制： 1 2 4 8 16 32 64 128 256 .....
下图是十进制数的斜二进制表示和二进制表示的对比：
根据上图可以看到只有最低非零位可以为2。
而给定一个十进制数转成斜二进制的方法我还没有找到资料，但是可以顺推出来，或者拼凑法。
现在来描述一下斜二进制的加一的情况，分两种情况：
1、如果最低非0位不是2，则加一的时候最低位增加一即可，操作就完成了。比如十进制4斜二进制的表示
是11，加一，变成12。
2、如果最低非0位是2，则加一的时候，直接将2变成0，然后2的高一位加一，操作就完成了。
比如十进制13，斜二进制表示是120，加一变成200。
这两种情况参照上图就很清楚了，还有进位只会产生一次是什么情况。
类似二项堆，斜二项堆由斜二项树组成。
斜二项树(skew binomial tree)：
定义：
1、一个rank为0的斜二项树是一个单节点；
2、一个rank为r+1的斜二项树包括以下3种情况：
a、由两个rank为r斜二项树通过简单链接而成，简单链接就是和二项树链接一样，其中一棵树作为另外一棵树的
最左子树；
b、A型斜链接，让两个rank为r的斜二项树作为一棵rank为0的树的子树。
c、B型斜链接，让rank为0的树和其中一个rank为r的斜二项树作为另外一个rank为r的树的最左子树，
rank为0的树放在最左边。
上图解释rank为r + 1的斜二项树的3种情况：
从上图可以看出当r=0时，A型和B型斜链接是相等的。还有二项树和完全平衡二叉树是斜二项树的特例，
相当于，如果只允许简单链接，则斜二项树就变成二项树，如果只允许A型链接则斜二项树就变成
完全平衡二叉树。
现在来看看斜二项树的大小，如果一棵rank为r的斜二项树只通过A型和B型链接构成，
则该树包含2^(r+1) - 1个节点。
不过一般来说，一个rank为r的斜二项树的大小为t，t满足 2^r <= | t | <= 2^(r+1) - 1。
由斜二项树的定义，我们知道和二项树不同的是rank相同的斜二项树的形状大小是可以不相同的。
下面上图举例rank为2的斜二项树的所有可能形状（rank为2的斜二项树大小为 4 ~ 7）：
同样一棵斜二项树是堆有序的，如果树上的每个节点都比它的子节点要小。为了维护堆顺序，
做简单链接时和二项树相同，做A型链接时，rank为0的树根需要是最小，B型链接其中一棵rank为r的树根最小。
斜二项堆：
类似二项堆的定义，斜二项堆是堆有序的斜二项树森林，每棵树的rank都不一样，除了rank值最小的树可以同时
存在两棵。因为rank值相同的斜二项树的形状也不一定相同。所以给定斜二项堆的大小，所包含的二项树也不一样。
比如，大小为4的斜二项堆有四种形态：
1、包含一棵rank为2大小为4的二项树；
2、包含两棵rank为1的树，每棵树大小为2；
3、包含1棵rank为1大小为3的树和一棵rank为0的树；
4、包含一棵rank为1大小为2的树和两棵rank为0的树。
查找堆中的最小元素（findMin）操作和合并两个堆（meld）操作和二项堆差不多。为了查找堆中的最小元素，
只需要遍历一次所有树的根，时间复杂度还是O(log n)。而对于合并操作，首先对两个要合并的堆做一些处理，
就是如果堆中rank最小的树存在两棵，则将这两棵树做个简单链接，然后才进行两个堆的合并，接下来的
合并的过程和二项堆的就一样了，如果找到两个rank相同的树，就将这两棵树做一个简单链接
（在合并过程中都是用简单链接），然后再将结果合并到由剩下的树合并而成的堆中时间复杂度也是O(log n)。
而斜二项堆的最大优点就是上面也提到过的，插入一个新的元素时间复杂度为O(1)。
在插入一个新的元素时，首先新建一棵rank为0的树，然后我们察看堆中的rank最小两棵斜二项树，
如果这两棵树的rank值相同，则将这两棵树和新建的树做一个斜链接（是A型或B型链接看具体的情况），
得到的rank为r + 1的斜二项树就是堆中rank最小的树，直接加进堆中即可。
如果rank最小的两棵树的rank值不相同，则我们只需把新建的节点加入堆中即可，无需其他操作，因为
这时堆中最多可能存在一棵rank为0的树。
对于删除最小元素的操作，首先还是先找到最小元素所在的树，然后把树根删除，接着把子树进行分组，
rank为0的分一组，rank不为0的分一组，rank不为0的子树也是斜二项树。然后把rank不为零的树和原来的堆合并，
最后把rank为零的组逐个插入到堆中，论文中说复杂度是O(log n)，其实认真想一下，
找最小是O(log n)，分组的时间复杂度和子树的大小有关，然后合并O(log n)，单独插入每个元素常数是常数时间，
总的复杂度也应该和个数有关。
斜二项堆定义：
斜二项堆定义（参考二项树的定义写成）：
// 对应论文第12和13页，Figure 6 和 7
trait SkewBinomialHeap 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
//和二项树定义相同
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 skewLink( t0: Node, t1: Node, t2: Node): Node = {
if ( ord.lteq( t1.x, t0.x ) && ord.lteq( t1.x, t2.x ) ) //B型斜链接
Node( t1.x, t1.r + 1, t0 :: t2 :: t1.c )
else if( ord.lteq( t2.x, t0.x ) && ord.lteq( t2.x, t1.x ) ) //B型斜链接
Node( t2.x, t2.r + 1, t0 :: t1 :: t2.c )
else //A型斜链接
Node( t0.x, t1.r + 1, List(t1, t2) )
}
protected def ins( t: Node, ts: H ): H = ts match {
case Nil => List(t)
case tp :: ts => // 同样也只存在t.r <= tp.r
if ( t.r < tp.r ) t :: tp :: ts else ins( link( t, tp ), ts )
}
//如果堆中rank最小的两棵树的rank值相同，则将这两棵树链接
protected def uniqify( ts: H ): H = ts match {
case Nil => empty
case t :: ts => ins( t, ts )
}
//和二项树的合并逻辑相同
protected def meldUniq( ts1: H, ts2: H ): H = (ts1, ts2) match {
case ( Nil, ts ) => ts
case ( ts, Nil ) => ts
case ( t1 :: ts1, t2 :: ts2 ) =>
if ( t1.r < t2.r ) t1 :: meldUniq( ts1, t2 :: ts2 )
else if ( t2.r < t1.r ) t2 :: meldUniq( t1 :: ts1, ts2 )
else ins( link( t1, t2 ), meldUniq( ts1, ts2 ) )
}
override def empty = Nil
override def isEmpty( ts: H ) = ts.isEmpty
override def insert( x: A, ts: H ) = ts match {
case t1 :: t2 :: rest =>
if ( t1.r == t2.r ) skewLink(Node( x, 0, empty), t1, t2) :: rest
else Node( x, 0, empty) :: ts
case _ => Node( x, 0, empty) :: ts
}
override def meld( ts1: H, ts2: H ) = meldUniq( uniqify( ts1 ), uniqify( ts2 ) )
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 )
case tp :: tsp =>
val ( tq, tsq ) = getMin( tp, tsp )
if ( ord.lteq( root( t ), root( tq ) ) ) ( t, ts )
else ( tq, t :: tsq )
}
//辅助函数，将被删除的树的子树进行分组，rank大于0的一组
//也就是返回值H，rank等于0的分为一组也就是List[A]
def split( ts: H, xs: List[A], c: H ): ( H, List[A] ) = c match {
case Nil => ( ts, xs )
case t :: c =>
if ( t.r == 0 ) split( ts, root( t ) :: xs, c )
else split( t :: ts, xs, c )
}
val ( Node( _, _, c ), tsq ) = getMin( t, ts )
val ( tsr, xsr ) = split( empty, List[A](), c ) //对子树进行分组
val m = meld( tsq, tsr ) //将rank大于0的子树tsr合并到tsq堆中
( m /: xsr)( (h, x) => insert( x , h ) )
//等价于 xsr.foldLeft( m )( ( h, x ) => insert( x , h ) )，
//将rank小于0的树的值插入到新堆中
}
}对斜二项堆还是不太了解的读者可以看看这个pdf文档： Skew Binomial Heap
对函数式数据结构有兴趣的读者还可以看看这个pdf文档： Purely Functional Data Structures 。
斜二项堆的介绍就到这里，part three将会介绍剩下的优化。