0001 #include <windows.h>
0002 #include "PQ_test.h"
0003 
0004 template <typename PQ> void testPq(Rank n) { //统一测试基于列表、向量以及左式堆实现的优先级队列
0005    Rank s = 2*n/3; Rank* A = new Rank[s]; //创建容量为2*n/3的数组，且
0006    for (Rank i = 0; i < s; i++) A[i] = dice(3*n); //所有元素随机
0007    printf("Creating a heap of size %d from %d random keys:\n", n/3, s);
0008    for (Rank i = 0; i < s; i++) print(A[i]); printf("\n");
0009    PQ heap(A + n/6, n/3); delete[] A; //批量建堆（ComplHeap实现了Robert Floyd算法）
0010    print(heap);
0011    while (heap.size() < n) { //随机测试
0012       if (dice((Rank) 100) < 70) //70%概率插入新元素
0013          { Rank e = dice(3*n); printf("insert("); print(e); printf(")\n"); heap.insert(e); }
0014       else //30%概率摘除最大元素
0015          if (!heap.empty())
0016             { printf("delMax() ="); print(heap.delMax()); printf("\n"); }
0017       print(heap);
0018    }
0019    while (!heap.empty()) //清空
0020       { printf("delMax() ="); print(heap.delMax()); printf("\n"); }
0021    print(heap);
0022    while (heap.size() < n/23) //随机插入
0023       { Rank e = dice(3*n); printf("insert("); print(e); printf(")\n"); heap.insert(e); }
0024    print(heap);
0025    while (!heap.empty()) //再次清空
0026       { printf("delMax() ="); print(heap.delMax()); printf("\n"); }
0027    print(heap);
0028 } //TestPq
0029 
0030 int main(int argc, char* argv[]) {
0031    SetConsoleOutputCP(CP_UTF8); SetConsoleCP(CP_UTF8);
0032    if (2 > argc) { printf("Usage: %s <size of test>\a\a\n", argv[0]); return 1; }
0033    srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0034 #if defined(DSA_PQ_LEFTHEAP)
0035    testPq<LeftHeap<Rank>>(atoi(argv[1])); //元素类型可以在这里任意选择
0036 #elif defined(DSA_PQ_COMPLHEAP)
0037    testPq<ComplHeap<Rank>>(atoi(argv[1])); //元素类型可以在这里任意选择
0038 #elif defined(DSA_PQ_LIST)
0039    testPq<ListPQ<Rank>>(atoi(argv[1])); //元素类型可以在这里任意选择
0040 #else
0041    printf("Unrecognized PQ type\n");
0042 #endif
0043    return 0;
0044 }