/* * Internal method to merge two roots * Deals with deviant cases and calls recursive merge1. */ LeftistNode * merge( LeftistNode *h1, LeftistNode *h2 ) {   if( h1 == NULL )     return h2;   if( h2 == NULL )     return h1;   if( h1->element < h2->element )     return merge1( h1, h2 );   else     return merge1( h2, h1 ); }

  合并左式堆的实际方法。

/* * Internal method to merge two roots * Assumes trees are not empty,and h1`s root contains smallest item. */ LeftistNode *merge1( LeftistNode *h1, LeftistNode *h2 ){  if( h1->left == NULL ) // single node    h1->left = h2; // Other fields in h1 already accurate  else  {    h1->right = merge( h1->right, h2 );    if( h1->left->npl < h1->right->npl )      swapChildren( h1 );    h1->npl = h1->right->npl + 1;    }  return h1;}

  执行合并的时间与右路径的长的和成正比，因为在递归调用期间对每一个被访问的节点执行的是常数工作量。因此合并两个左式堆的时间界为Ο(logN)。

  也可以分两次来非递归实施该操作。第一次，通过合并两个堆的右路径建立一棵新的树，以排序的方式安排H1和H2右路经上的节点，保持它们各自的左儿子不变。第二次，构成堆，儿子的交换工作在左式堆性质被破坏的节点上进行。递归过程和非递归过程的结果是相同的。

 

图5-21 合并H1和H2的右路径的结果

  下面是左式堆的插入方法。

/** * Insers x; duplicates allowed. */ void insert( const Comparable & x ) {   root = merge( new LeftistNode( x ), root ); }

  下面是左堆式的deleteMin方法。

/** * Remove the minimum item * Throws underflowException if empty. */void deleteMin(){  if( isEmpty() )    throw UnderflowException();      LeftistNode *oldRoot = root;  root = merge( root->left, root->right );  delete oldRoot; }/** * Remove the minimum item * Throws underflowException if empty. */ void deleteMin( Comparable & minItem )  {   minItem = findMin();   deleteMin(); }

  最后，可以通过建立二叉堆（显然是使用链接实现）来以Ο(N)时间建立左式堆。

 

 5.7 斜堆

  斜堆（skew heap）是左式堆的自调节形式，实现起来极其简单。斜堆和左式堆间的关系类似于伸展树和AVL树间的关系。斜堆是具有堆序的二叉树，但是不存在对树的结构限制。不同于左式堆，关于任何节点的零路径长的任何信息都不保留。斜堆的右路经在任何时刻都可以任意长，因此所有操作最坏的情形是Ο(N)。正如伸展树一样，对任意M次操作，总的坏情形运行时间是Ο(MlogN)。因此，斜堆的每次操作摊还开销（amortized cost）为Ο(logN)。

  斜堆的交换是无条件的，除右路经上所有节点的最大者不交换它的左右儿子之外，我们都要进行交换。输入和前面相同。

图5-22 两个斜堆H1和H2

  如果我们递归地将H2与H1的根在8处的子堆合并，那么我们得到5-23中的堆。

图5-23 将H2与H1的右子堆合并的结果

  这也是递归完成的。我们使这个堆称为H1的新左儿子，而H1的老的左儿子变成了新的右儿子。

图5-24 合并斜堆H1和H2的结果

 5.8 二项队列

  二项队列支持所有合并、插入和deleteMin操作。每次操作的最坏运行时间是Ο(logN)，而插入操作平均时间为常数。

  5.8.1 二项队列结构

  二项队列（binomial queue）不同于前面介绍的所有优先队列的实现之处在于，一个二项队列不是一棵堆序的树，而是堆序的树的集合，称为森林（forest）。堆序树中的每一棵都是有约束的形式，叫做二项树（binomial tree）。每一个高度上至多存在一棵二项树。高度为0的二项树是一棵单节点树;高度为k的二项树Bk通过将一棵二项树Bk-1附接到另一棵二项树Bk-1的根上而构成。如下图所示;

图5-25 二项树B0、B1、B2、B3以及B4

  从图中可以看出，二项树Bk由一个带有儿子B0，B1，…，Bk-1的根组成。高度为k的二项树恰好有2^k个节点，而在深度为d处的节点处为二项系数（k d）。如果我们把堆序施加到二项树上并允许任意高度上最多一棵二项树，那么我们能用二项树的集合唯一地表示任意大小的优先队列。下面是6个元素的优先队列的例子。

图5-26 具有6个元素的二项队列H1

  5.8.2 二项队列操作

  最小元可以通过搜索所有树的根来找出。由于最多有logN棵不同的树，因此最小元可以以Ο(logN)时间找到。另外，如果我们记住最小元在其他操作期间变化更新它，那么也可保留最小元的信息并以Ο(1)时间执行该操作。

  合并两个二项队列在概念上是一个容易的操作。如下例子：

图5-27 两个二项队列H1和H2

  合并操作基本上是通过将两个队列加到一起来完成的。将H1和H2高度为1的二项树合并为高度为2的二项树，高度为2的二项树合并为高度为3的二项树。

图5-28 H1和H2中两棵B1树合并

图5-29 二项队列H3：合并H1和H2的结果

  合并两棵二项树均花费常数时间，而总共存在Ο(logN)棵二项树，因此合并的最坏时间为Ο(logN)。

  下面是一个插入的例子，我们用图5-30到图5-36来演示依次插入1～7来构成一个二项队列。

图5-30 在插入1之后

图5-31 在插入2之后

图5-32 在插入3之后

图5-33 在插入4之后

图5-34 在插入5之后

图5-35 在插入6之后

图5-36 在插入7之后

  deleteMin可以通过首先找出一棵具有一棵具有最小根的二项树来完成。令该树为BK，并令原始优先队列为H。我们从H的树的森林中除去二项树Bk，形成新的二项树队列H'。再除去Bk的根，得到一些二项树B0，B1，…，Bk-1，它们共同形成优先队列H''。合并H'和H''，操作结束。

  作为例子，对H3执行一次deleteMin。如下图：

图5-37 二项队列H3

图5-38 二项队列H’，包含除B3外的H3中所有的二项树

图5-39 二项队列H''：除去12后的B3

图5-40 deleteMin应用到H3的结果

  deleteMin操作将原二项队列一分为2。找出含有最小元素的树并创建队列H'和H''花费Ο(logN)时间。合并这两个队列又花费Ο(logN)时间。因此，整个deleteMin操作花费Ο(logN)时间。

 

  5.8.3 二项队列的实现

  deleteMIn操作需要快速找出根的所有子树的能力，因此，需要一般树的标准表示方法：每个节点的儿子都在一个链表中，而且每个节点都有一个指向它的第一个儿子（如果有的话）的指针。该操作还要求诸儿子按照它们的子树的大小排序。该操作还要求诸儿子按照它们的子树的大小排序。我们还要保证很容易合并两棵树。

  总之，二项树的每一个节点将包含数据、第一个儿子以及右兄弟。二项树中儿子以递减次序排序。图5-42说明了如何表示5-41的二项队列。下面是类架构代码。

图5-41 画成森林的二项队列H3

图5-42 二项队列H3的表示方式

template
    
     class BinomialQueue{  public:    BinomialQueue();    BinomialQueue( const Comparable & Item );    BinomialQueue( const BinomialQueue & rhs );    ~BinomialQueue();        bool isEmpty() const;    const Comparable & findMin() const;        void insert( const Comparable & x );    void deleteMin();    void deleteMin( Comparable & minItem );        void makeEmpty();    void merge( BinomialQueue & rhs );        const BinomialQueue & operator= ( const BinomialQueue & rhs );      private:    struct BinomialNode    {      Comparable element;      BinomialNode *leftChild;      BinomialNode *nextSibling;            BinomialNode( const Comparable & theElement, BinomialNode *lt, BinomialNode *rt  )        : element( theElement ), leftChild( lt ), nextSibling( rt ) {  }    };        enum { DEFAULT_TREES = 1 };        int currentSize; // Number of items in priority queue    vector
     
       theTrees; // An array of tree roots        int findMinIndex() const;    int capacity() const;    BinomialNode * combineTrees( BinomialNode *t1, BinomialNode *t2 );    void makeEmpty( BinomialNode * & t );    BinomialNode * clone( BinomialNode *t ) const;   };
     
    

  为了合并两个二项队列，我们需要一个方法来合并两棵同样大小的二项树。如下图：

/** * Return the result of merging equal-sized t1 and t2 */ BinomialNode * combineTrees( BinomialNode *t1, BinomialNode *t2 ) {   if( t2->element < t1->element )     return combineTrees( t2, t1 );   t2->nextSibling = t1->leftChild;   t1->leftChild = t2;   return t1; }

  下面是合并两个优先队列的方法。

/** * Merge rhs into the priority queue * ths becomes empty.rhs must be different from this. */ void merge( BinomialQueue & rhs ) {   if( this == &rhs ) // Avoid aliasing problems     return;        currentSize += rhs.currentSize;      if( currentSize > capacity() )   {     int oldNumTree = theTrees.size();     int newNumTrees = max( theTree.size(), rhs.theTrees.size() ) + 1;     theTrees.resize( newNumTrees );     for( int i = oldNumTrees; i < newNumTrees; i++ )       theTrees[ i ] = NULL;   }      BinomialNode *carry = NULL;   for( int i = 0, j = 1; j <= currentSize; i++, j *= 2 )   {     BinomialNode *t1 = theTrees[ i ];     BinomialNode *t2 = i < rhs.theTree.size() ? rhs.theTrees[ i ] : NULL;          int whichCase = t1 ==NULL ? 0 : 1;     whichCase += t2 == NULL ? 0 : 4;          swicth( whichCase )     {       case 0: // No trees       case 1: // Only this         break;       case 2: // Only rhs         thrTrees[ i ] = t2;         rhs.theTrees[ i ] = NULL;         break;       case 4: // Only carry         theTrees[ i ] = carry;         carry = NULL;         break;         case 3: // this and rhs           carry = combineTrees( t1, t2 );           theTrees[ i ] = rhs.theTrees[ i ] = NULL;           break;         case 5: // this and carry           carry = combineTrees( t1, carry );           theTrees[ i ] = NULL;           break;         case 6: // rhs and carry           carry = combineTrees( t2, carry );           rhs.theTrees[ i ] = NULL;           break;         case 7: // All trees           theTrees[ i ] = carry;           carry = combineTrees( t1, t2 );           rhs.theTrees[ i ] = NULL;           break;     }   }      for( int k = 0; k < rhs.theTrees.size(); k++ )     rhs.theTrees[ k ] = NULL;   rhs.currentSize = 0; }

 5.9 标准库中的优先队列

  在STL中，二叉堆通过称为priority_queue的类模板实现的，STL实现一个最大堆（max-heap）而不是最小堆（min-heap）。于是所访问的就是最大项而不是最小项。键的成员如下：

void push( const Object & x );const Object & top() const;void pop();bool empty();void clear();

  下面是一个测试程序，表示priority_queue类模板在默认值为最大堆和最小堆的两种情况。

/** * Remove the minimum item and place it in minitem. * Throw UnderflowException if empty. */ void deleteMin( Comparable & minItem ) {   if( isEmpty() )     throw UnderflowException();        int minIndex = findMinIndex();   minItem = theTrees[ minIndex ]->element;      BinomialNode *oldRoot = theTrees[ minIndex ];   BinomialNode *deleteTree = oldRoot->leftChild;   delete oldRoot;      // Construct H''   BinomialQueue deleteQueue;   deleteQueue.theTrees.resize( minIndex + i );   deleteQueue.currentSize = ( 1 << minIndex ) - 1;   for( int j = minIndex - 1; j >= 0; j-- )   {     deleteQueue.theTree[ j ] = deletedTree;     deletedTree = deletedTree->nextSibling;     deleteQueue.thetree[ j ]->nextSibling = NULL;   }      // Construct H'   theTrees[ minIndex ] = NULL;   currentSize -= deleteQueue.currentSize + 1;      merge( deleteQueue ); }  /**  * Find index of tree containing the smallest item in the priority queue.  * The priority queue must not be empty.  * Return the index of tree containing the smallest item.  */  int findMinindex() const  {    int i;    int minIndex;        for( i = 0; theTrees[ i ] == NULL; i++ )      ;          for( minIndex = i; i < theTrees.size(); i++ )      if( theTrees[ i ] != NULL && theTrees[ i ]->element < theTrees[ minIndex ]->element )        minIndex = i;             return minIndex;  }

  下面是一个priority_queue的一个例子，注释说明了期望的输出顺序。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;template 
        
         void dumpContents( const string & msg, PriorityQueue & pq ){  cout << msg << ":" << endl;  while( !pq.empty() )  {    cout << pq.top() << endl;    pq.pop();  }}// Do some inserts and remove( done in dumpContents ).int main(){  priority_queue
         
           maxPQ;  priority_queue
          
           
            , greater
            
              > minPQ;    minPQ.push( 4 );  minPQ.push( 3 );  minPQ.push( 5 );  maxPQ.push( 4 );  maxPQ.push( 3 );  maxPQ.push( 5 );    dumpContents( "minPQ", minPQ ); // 3 4 5  dumpContents( "maxPQ", maxPQ ); // 5 4 3    return 0;}