纯函数式堆（纯函数式优先级队列）part one ----二项堆

//对应论文第三页，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
  
}

// 对应论文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 )  //将被删除节点的子树和剩下的树合并
  }
}