二项队列

  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 problems
166             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 BinomialNode
230     {
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 roots
245     int currentSize;                  // Number of items in the priority queue
246     
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( ) const
253     {
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( ) const
272       { 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 ) const
304     {
305         if( t == nullptr )
306             return nullptr;
307         else
308             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         else
18             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 }