数据结构二项队列

实现:

  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;
         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 
         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 = 100;
 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 }

 

更多相关文章
  • 工厂模式的话一般多写个工厂类,客户端代码多引用一个工厂类. 如果用基类的静态函数实现这个工厂类的话,工厂类就不必要了. 比如A是基类,B,C是它的子类.可以这样写: in A.H: class A { static A* factoryMethod(int category); }; in A.C: ...
  •  EasyFuzzer是一款新的模糊测试工具.目前只支持文件格式的模糊测试. 特点是:容易,精简,高效,智能. 容易:非常容易上手,不需要什么配置.有了他小学生也可以挖漏洞了,再也不愁没有0day了. 精简:为了容量和速度,软件采用100%汇编语言编写.排除了以往fuzzer的无用功能.绿色软件. ...
  • 聚集索引表插入数据和删除数据的方式是怎样的  根据<SQLSERVER聚集索引与非聚集索引的再次研究(上)>里说的,聚集索引维护着创建第一个聚集索引时的第一个字段的顺序来排序 当插入记录的时候,或者重新组织索引的时候都会按照字段顺序来排序 今天来做一个实验来验证一下  --华丽的 先创建 ...
  • 刚说完虚拟运营商集中走差异化.多品类.优服务战略,和迪信通虚拟业务部总经理黄建辉对虚拟运营服务前景的担忧,迪信通上市后首日的成绩就传过来了. 根据之前的招股书,迪信通上市暂定全球发售 166,667, 股,每股H股最高发行价 7.1 港币,最低5.3港币.今天上市开盘价为5.3港币,与最低发行价持平 ...
  • 一.生成APK Build-->Generate Signed APK... 以上是创建密钥库及密钥,创建后会自动选择刚创建的密钥库和密钥.若已经创建过输入password即可. 若第一次或需要新建点击Create new... Key store path:密钥库文件的地址 Password ...
  • 构思: 在首页(MainPage)上定义一个代表应用版本号的字符串,网站上写一个接口(让这个字符串与你的最新应用版本号进行比较,返回应用的ContentIdentifier与操作状态什么的). 一.wp客户端 using System; using System.Collections.Generi ...
一周排行
  •   方法描述 bind() 向匹配元素附加一个或更多事件处理器 blur() 触发.或将函数绑定到指定元素的 blur 事件 change() 触发.或将函数绑定到指定元素的 change 事件 click() 触发 ...
  • 了解一些关于策略路由配置还是很有用的,这里我们主要介绍基于源地址的策略路由配置,基于策略的路由为网络管理者提供了比传统路由协议对报文的转发和存储更强的控制能力,传统上,路由器用从路由协议派生出来的路由表,根据目的地址 ...
  • http-关于application/x-www-form-urlencoded等字符编码的解释说明 在Form元素的语法中,EncType表明提交数据的格式 用 Enctype 属性指定将数据回发到服务器时浏览器使 ...
  • 快速热身: Cookie可以用来通过浏览器在客户端存储相关用户信息. Cookie是Web服务器发送到浏览器,并且存储在客户端计算机磁盘中的一些文本信息 . 在浏览器发送一个请求到Web服务器时,如果Cookie没有 ...
  • 一.什么是观察者模式?   把现实世界中的报纸与订阅者的关系抽象出来就是观察者模式,一种报纸对应多个订阅者,订阅者可以随时解除订阅,未订阅的读者也可以随时开始订阅.一旦有新报纸发布,所有的订阅者都会收到新内容.   ...
  • 1.Shell概述    Shell是一个命令行解释器.它为用户提供了一个向Linux内核发送请求一以便运行程序的界面系统级程序,用户可以用 Shell来启动.挂起.停止甚至是编写一些程序    Shell还是一个功 ...
  • 处理应用程序或驱动程序的中断需要两个步骤.首先,中断必须使用关联的事件进行初始化.其次,IST  必须等待响应内核中断的中断事件.中断初始化以下示例代码将设置  IST  并将  IST  与特定的中断相关联.初始化 ...
  • http://www.tuicool.com/articles/mIJnumB   #ifdef的用法    灵活使用#ifdef指示符,我们可以区隔一些与特定头文件.程序库和其他文件版本有关的代码.代码举例:新建d ...
  • 属性 属性的作用就是保护字段,对字段的赋值和取值进行限定 属性的本质就是两个方法,一个叫get()对取值进行限定,一个叫set()对存值进行限定,属性只是对属性的再赋值. 如果只有get是只读属性,set是只写属性. ...
  • 中国联通昨日宣布与西班牙电信于23日签署协议,并同意互相增持对方约5亿美元的股份.此次交易完成后,中国联通对西班牙电信的持股比例将提高至1.37%,而西班牙电信对中国联通的持股比例将提高至约9.7%. 根据协议,双方 ...