1 #ifndef BINOMIAL_QUEUE_H  2 #define BINOMIAL_QUEUE_H  3   4 #include <iostream>  5 #include <vector>  6 #include "dsexceptions.h"  7 using namespace std;  8   9 // Binomial queue class 10 // 11 // CONSTRUCTION: with no parameters 12 // 13 // ******************PUBLIC OPERATIONS********************* 14 // void insert( x )       --> Insert x 15 // deleteMin( )           --> Return and remove smallest item 16 // Comparable findMin( )  --> Return smallest item 17 // bool isEmpty( )        --> Return true if empty; else false 18 // void makeEmpty( )      --> Remove all items 19 // void merge( rhs )      --> Absorb rhs into this heap 20 // ******************ERRORS******************************** 21 // Throws UnderflowException as warranted 22  23 template <typename Comparable> 24 class BinomialQueue 25 { 26   public: 27     BinomialQueue( ) : theTrees( DEFAULT_TREES ) 28     { 29         for( auto & root : theTrees ) 30             root = nullptr; 31         currentSize = 0; 32     } 33  34     BinomialQueue( const Comparable & item ) : theTrees( 1 ), currentSize{ 1 } 35       { theTrees[ 0 ] = new BinomialNode{ item, nullptr, nullptr }; } 36  37     BinomialQueue( const BinomialQueue & rhs ) 38       : theTrees( rhs.theTrees.size( ) ),currentSize{ rhs.currentSize } 39     {  40         for( int i = 0; i < rhs.theTrees.size( ); ++i ) 41             theTrees[ i ] = clone( rhs.theTrees[ i ] ); 42     } 43  44     BinomialQueue( BinomialQueue && rhs ) 45       : theTrees{ std::move( rhs.theTrees ) }, currentSize{ rhs.currentSize } 46     {  47     } 48  49     ~BinomialQueue( ) 50       { makeEmpty( ); } 51  52      53     /** 54      * Deep copy. 55      */ 56     BinomialQueue & operator=( const BinomialQueue & rhs ) 57     { 58         BinomialQueue copy = rhs; 59         std::swap( *this, copy ); 60         return *this; 61     } 62          63     /** 64      * Move. 65      */ 66     BinomialQueue & operator=( BinomialQueue && rhs ) 67     { 68         std::swap( currentSize, rhs.currentSize ); 69         std::swap( theTrees, rhs.theTrees ); 70          71         return *this; 72     } 73      74     /** 75      * Return true if empty; false otherwise. 76      */ 77     bool isEmpty( ) const 78       { return currentSize == 0; } 79  80     /** 81      * Returns minimum item. 82      * Throws UnderflowException if empty. 83      */ 84     const Comparable & findMin( ) const 85     { 86         if( isEmpty( ) ) 87             throw UnderflowException{ }; 88  89         return theTrees[ findMinIndex( ) ]->element; 90     } 91      92     /** 93      * Insert item x into the priority queue; allows duplicates. 94      */ 95     void insert( const Comparable & x ) 96       { BinomialQueue oneItem{ x }; merge( oneItem ); } 97  98     /** 99      * Insert item x into the priority queue; allows duplicates.100      */101     void insert( Comparable && x )102       { BinomialQueue oneItem{ std::move( x ) }; merge( oneItem ); }103     104     /**105      * Remove the smallest item from the priority queue.106      * Throws UnderflowException if empty.107      */108     void deleteMin( )109     {110         Comparable x;111         deleteMin( x );112     }113 114     /**115      * Remove the minimum item and place it in minItem.116      * Throws UnderflowException if empty.117      */118     void deleteMin( Comparable & minItem )119     {120         if( isEmpty( ) )121             throw UnderflowException{ };122 123         int minIndex = findMinIndex( );124         minItem = theTrees[ minIndex ]->element;125 126         BinomialNode *oldRoot = theTrees[ minIndex ];127         BinomialNode *deletedTree = oldRoot->leftChild;128         delete oldRoot;129 130         // Construct H‘‘131         BinomialQueue deletedQueue;132         deletedQueue.theTrees.resize( minIndex );133         deletedQueue.currentSize = ( 1 << minIndex ) - 1;134         for( int j = minIndex - 1; j >= 0; --j )135         {136             deletedQueue.theTrees[ j ] = deletedTree;137             deletedTree = deletedTree->nextSibling;138             deletedQueue.theTrees[ j ]->nextSibling = nullptr;139         }140 141         // Construct H‘142         theTrees[ minIndex ] = nullptr;143         currentSize -= deletedQueue.currentSize + 1;144 145         merge( deletedQueue );146     }147 148     /**149      * Make the priority queue logically empty.150      */151     void makeEmpty( )152     {153         currentSize = 0;154         for( auto & root : theTrees )155             makeEmpty( root );156     }157 158     /**159      * Merge rhs into the priority queue.160      * rhs becomes empty. rhs must be different from this.161      * Exercise 6.35 needed to make this operation more efficient.162      */163     void merge( BinomialQueue & rhs )164     {165         if( this == &rhs )    // Avoid aliasing problems166             return;167 168         currentSize += rhs.currentSize;169 170         if( currentSize > capacity( ) )171         {172             int oldNumTrees = theTrees.size( );173             int newNumTrees = max( theTrees.size( ), rhs.theTrees.size( ) ) + 1;174             theTrees.resize( newNumTrees );175             for( int i = oldNumTrees; i < newNumTrees; ++i )176                 theTrees[ i ] = nullptr;177         }178 179         BinomialNode *carry = nullptr;180         for( int i = 0, j = 1; j <= currentSize; ++i, j *= 2 )181         {182             BinomialNode *t1 = theTrees[ i ];183             BinomialNode *t2 = i < rhs.theTrees.size( ) ? rhs.theTrees[ i ] : nullptr;184 185             int whichCase = t1 == nullptr ? 0 : 1;186             whichCase += t2 == nullptr ? 0 : 2;187             whichCase += carry == nullptr ? 0 : 4;188 189             switch( whichCase )190             {191               case 0: /* No trees */192               case 1: /* Only this */193                 break;194               case 2: /* Only rhs */195                 theTrees[ i ] = t2;196                 rhs.theTrees[ i ] = nullptr;197                 break;198               case 4: /* Only carry */199                 theTrees[ i ] = carry;200                 carry = nullptr;201                 break;202               case 3: /* this and rhs */203                 carry = combineTrees( t1, t2 );204                 theTrees[ i ] = rhs.theTrees[ i ] = nullptr;205                 break;206               case 5: /* this and carry */207                 carry = combineTrees( t1, carry );208                 theTrees[ i ] = nullptr;209                 break;210               case 6: /* rhs and carry */211                 carry = combineTrees( t2, carry );212                 rhs.theTrees[ i ] = nullptr;213                 break;214               case 7: /* All three */215                 theTrees[ i ] = carry;216                 carry = combineTrees( t1, t2 );217                 rhs.theTrees[ i ] = nullptr;218                 break;219             }220         }221 222         for( auto & root : rhs.theTrees )223             root = nullptr;224         rhs.currentSize = 0;225     }    226 227 228   private:229     struct BinomialNode230     {231         Comparable    element;232         BinomialNode *leftChild;233         BinomialNode *nextSibling;234 235         BinomialNode( const Comparable & e, BinomialNode *lt, BinomialNode *rt )236           : element{ e }, leftChild{ lt }, nextSibling{ rt } { }237         238         BinomialNode( Comparable && e, BinomialNode *lt, BinomialNode *rt )239           : element{ std::move( e ) }, leftChild{ lt }, nextSibling{ rt } { }240     };241 242     const static int DEFAULT_TREES = 1;243 244     vector<BinomialNode *> theTrees;  // An array of tree roots245     int currentSize;                  // Number of items in the priority queue246     247     /**248      * Find index of tree containing the smallest item in the priority queue.249      * The priority queue must not be empty.250      * Return the index of tree containing the smallest item.251      */252     int findMinIndex( ) const253     {254         int i;255         int minIndex;256 257         for( i = 0; theTrees[ i ] == nullptr; ++i )258             ;259 260         for( minIndex = i; i < theTrees.size( ); ++i )261             if( theTrees[ i ] != nullptr &&262                 theTrees[ i ]->element < theTrees[ minIndex ]->element )263                 minIndex = i;264 265         return minIndex;266     }267 268     /**269      * Return the capacity.270      */271     int capacity( ) const272       { return ( 1 << theTrees.size( ) ) - 1; }273 274     /**275      * Return the result of merging equal-sized t1 and t2.276      */277     BinomialNode * combineTrees( BinomialNode *t1, BinomialNode *t2 )278     {279         if( t2->element < t1->element )280             return combineTrees( t2, t1 );281         t2->nextSibling = t1->leftChild;282         t1->leftChild = t2;283         return t1;284     }285 286     /**287      * Make a binomial tree logically empty, and free memory.288      */289     void makeEmpty( BinomialNode * & t )290     {291         if( t != nullptr )292         {293             makeEmpty( t->leftChild );294             makeEmpty( t->nextSibling );295             delete t;296             t = nullptr;297         }298     }299 300     /**301      * Internal method to clone subtree.302      */303     BinomialNode * clone( BinomialNode * t ) const304     {305         if( t == nullptr )306             return nullptr;307         else308             return new BinomialNode{ t->element, clone( t->leftChild ), clone( t->nextSibling ) };309     }310 };311 312 #endif

 1 #include "BinomialQueue.h" 2 #include <iostream> 3 using namespace std; 4  5 int main( ) 6 { 7     int numItems = 100000; 8     BinomialQueue<int> h; 9     BinomialQueue<int> h1;10     BinomialQueue<int> h2;11     int i = 37;12 13     cout << "Begin test..." << endl;14     for( i = 37; i != 0; i = ( i + 37 ) % numItems )15         if( i % 2 == 0 )16             h1.insert( i );17         else18             h.insert( i );19 20     h.merge( h1 );21     h2 = h;22 23     for( i = 1; i < numItems; ++i )24     {25 26         int x;27         h2.deleteMin( x );28         if( x != i )29             cout << "Oops! " << i << endl;30     }31 32     if( !h1.isEmpty( ) )33         cout << "Oops! h1 should have been empty!" << endl;34 35     cout << "End of test... no output is good" << endl;36 37     return 0;38 }