0001 /******************************************************************************************
0002  * Test of PQ_ComplHeap & PQ_LeftHeap
0003  ******************************************************************************************/
0004 #include "PQ_test.h"
0005 //#include <windows.h>
0006 
0007 /******************************************************************************************
0008  * 针对基于列表、向量以及左式堆实现的优先级队列，做过程统一的测试
0009  ******************************************************************************************/
0010 template <typename PQ, typename T> void testHeap( Rank n ) {
0011    Rank s = 2*n/3; T* A = new T[s]; //创建容量为2*n/3的数组，且
0012    for ( T i = 0; i < 2 * (T)n / 3; i++ ) A[i] = dice( ( T ) 3 * n ); //所有词条随机
0013    PQ heap( A + n / 6, n / 3 ); //批量建堆（PQ_ComplHeap实现了Robert Floyd算法）
0014    delete [] A;
0015    while ( heap.size() < n ) { //随机测试
0016       if ( dice( 100 ) < 70 ) { //70%概率插入新词条
0017          T e = dice( ( T ) 3 * n );
0018          heap.insert( e );
0019       } else { //30%概率摘除最大词条
0020          if ( !heap.empty() ) {
0021             T e = heap.delMax();
0022          }
0023       }
0024    }
0025    while ( !heap.empty() ) { //清空
0026       T e = heap.delMax();
0027    }
0028 }
0029 
0030 /******************************************************************************************
0031  * 优先级队列测试
0032  ******************************************************************************************/
0033 int main( int argc, char* argv[] ) {
0034    if ( 2 > argc ) { printf( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; }
0035    srand((unsigned int)time(NULL)); //随机种子
0036    //srand( 31415926 ); //固定种子（假种子，调试用）
0037 #if defined(DSA_PQ_LEFTHEAP)
0038    testHeap<PQ_LeftHeap<int>, int>( atoi ( argv[1] ) ); //词条类型可以在这里任意选择
0039 #elif defined(DSA_PQ_COMPLHEAP)
0040    testHeap<PQ_ComplHeap<int>, int>( atoi ( argv[1] ) ); //词条类型可以在这里任意选择
0041 #elif defined(DSA_PQ_LIST)
0042    testHeap<PQ_List<int>, int>( atoi ( argv[1] ) ); //词条类型可以在这里任意选择
0043 #else
0044    printf( "PQ type not defined yet\n" );
0045 #endif
0046    return 0;
0047 }