1第6章優(yōu)先級(jí)隊(duì)列基本的優(yōu)先級(jí)隊(duì)列二叉堆D堆歸并優(yōu)先級(jí)隊(duì)列STL中的優(yōu)先級(jí)隊(duì)列排隊(duì)系統(tǒng)的模擬2二叉堆堆是一棵完全二叉樹，且滿足下述關(guān)系之一

ki≤k2i且ki≤k2i+1(i=1,2,…,n/2)或者：

ki≥k2i且ki≥k2i+1(i=1,2,…,n/2)其中，下標(biāo)是樹按層次遍歷的次序滿足前一條件的稱為最小化堆。例如:序列

{2,3,4,5,7,10,23,29,60}是最小化堆滿足后一條件的稱為最大化堆。例如:序列

{12,7,8,4,6,5,3,1}是最大化堆

3則這棵二叉樹滿足：對任一棵子樹，根結(jié)點(diǎn)的值大于兒子結(jié)點(diǎn)的值（最大化堆），或者根結(jié)點(diǎn)的值小于兒子結(jié)點(diǎn)的值（最小化堆）4836712515423732102960最大化堆最小化堆4二叉堆的特性結(jié)構(gòu)性：符合完全二叉樹的結(jié)構(gòu)有序性：滿足父節(jié)點(diǎn)小于子節(jié)點(diǎn)（最小化堆）或父節(jié)點(diǎn)大于子節(jié)點(diǎn)（最大化堆）以下的討論都以最小化堆為例5二叉堆的存儲(chǔ)可以采用順序存儲(chǔ)二叉堆的有序性可以很容易地通過下標(biāo)來反映5423732102960234571023296001234567896基于二叉堆的優(yōu)先級(jí)隊(duì)列

如果數(shù)值越小，優(yōu)先級(jí)越高，則可以用一個(gè)最小化堆存儲(chǔ)優(yōu)先級(jí)隊(duì)列在最小化堆中，最小元素是根元素，而根結(jié)點(diǎn)永遠(yuǎn)存放在數(shù)組的下標(biāo)為1的元素中。因此，獲取隊(duì)頭元素的操作就是返回下標(biāo)為1的數(shù)組元素值，出隊(duì)操作就是刪除下標(biāo)為1的數(shù)組元素中的值。入隊(duì)操作就是在數(shù)組的末尾添加一個(gè)元素，但添加后要調(diào)整元素的位置，以保持堆的有序性

。7優(yōu)先級(jí)隊(duì)列類數(shù)據(jù)成員：用一個(gè)動(dòng)態(tài)數(shù)組成員函數(shù)：實(shí)現(xiàn)隊(duì)列類的所有操作8優(yōu)先級(jí)隊(duì)列類的定義template<classType>classpriorityQueue{private:intcurrentSize;Type*array;intmaxSize;voiddoubleSpace();voidbuildHeap();voidpercolateDown(inthole);9public:priorityQueue(intcapacity=100) {array=newType[capacity];maxSize=capacity;currentSize=0;}priorityQueue(constTypedata[],intsize); ~priorityQueue(){delete[]array;}boolisEmpty()const{returncurrentSize==0;}

voidenQueue(constType&x);

TypedeQueue();TypegetHead(){returnarray[1];}};10enQueue（x）enQueue操作是在堆中插入一個(gè)新元素堆的插入通常是在具有最大序號(hào)的元素之后插入新的元素或結(jié)點(diǎn)。如果新元素放入后，沒有違反堆的有序性，那么操作結(jié)束。否則，讓該節(jié)點(diǎn)向父節(jié)點(diǎn)移動(dòng)，直到滿足有序性或到達(dá)根節(jié)點(diǎn)。新節(jié)點(diǎn)的向上移動(dòng)稱為向上過濾(percolateup)11在如下的堆中插入元素1的過程：542373210296054233210296071254233210296075423321102960713enQueue過程template<classType>voidpriorityQueue<Type>::enQueue(constType&x){if(currentSize==maxSize-1)doubleSpace();

//向上過濾

inthole=++currentSize;for(;hole>1&&x<array[hole/2];hole/=2)array[hole]=array[hole/2];array[hole]=x;}

14enQueue的時(shí)間效率最壞情況是對數(shù)的平均情況，過濾會(huì)提前結(jié)束。有資料表明，平均是2.6次比較，因此元素平均上移1.6層。15DeQueue操作當(dāng)最小元素被刪除時(shí)，在根上出現(xiàn)了一個(gè)空結(jié)點(diǎn)。堆的大小比以前小1，堆的結(jié)構(gòu)性告訴我們，最后一個(gè)結(jié)點(diǎn)應(yīng)該刪掉。如果最后一項(xiàng)應(yīng)該放在此空結(jié)點(diǎn)中，就把它放進(jìn)去。然而，這是不可能的。我們必須玩與插入操作相同的游戲：把某些項(xiàng)放入空結(jié)點(diǎn)，然后移動(dòng)空結(jié)點(diǎn)。僅有的區(qū)別在于：對DeQueue操作，空結(jié)點(diǎn)是往下移動(dòng)。過程：找到空結(jié)點(diǎn)的一個(gè)較小的子結(jié)點(diǎn)，如果該兒子的值小于我們要放入的項(xiàng)，則把該兒子放入空結(jié)點(diǎn)，把空結(jié)點(diǎn)往下推一層，重復(fù)這個(gè)動(dòng)作，直到該項(xiàng)能被放入正確的位置，這個(gè)過程稱為向下過濾（percolatedown）。1654233211029607542332102960542332102960542373210296017deQueue()

template<classType>TypepriorityQueue<Type>::deQueue(){TypeminItem;minItem=array[1];array[1]=array[currentSize--];percolateDown(1);returnminItem;}

18向下過濾template<classType>voidpriorityQueue<Type>::percolateDown(inthole){intchild;Typetmp=array[hole];

for(;hole*2<=currentSize;hole=child){child=hole*2;if(child!=currentSize&&array[child+1]<array[child])child++;if(array[child]<tmp)array[hole]=array[child];elsebreak;}array[hole]=tmp;}19deQueue操作的性能因?yàn)闃溆袑?shù)的深度，在最壞情況下，deQueue是一個(gè)對數(shù)時(shí)間的操作。根據(jù)堆的有序性，堆中最后一個(gè)結(jié)點(diǎn)的值一般都是比較大的。因此，向下過濾很少有提前一或二層結(jié)束的，所以deQueue操作平均也是對數(shù)時(shí)間。20建堆可以看成N次連續(xù)插入，其時(shí)間應(yīng)該是在O(NlogN)時(shí)間內(nèi)完成。事實(shí)上，在構(gòu)造過程中，我們并不關(guān)心每個(gè)元素加入后堆的狀態(tài)，我們關(guān)心的是N個(gè)元素全部加入后的最后狀態(tài)，最后的狀態(tài)是要保證堆的有序性。至于中間過程中的有序性是否成立并不重要。有了這個(gè)前提后，我們能將構(gòu)造堆的時(shí)間復(fù)雜度降到O（N）21建堆過程利用堆的遞歸定義如果函數(shù)buildHeap可以將一棵完全二叉樹調(diào)整為一個(gè)堆，那么，只要對左子堆和右子堆遞歸調(diào)用buildHeap。至此，我們能保證除了根結(jié)點(diǎn)外，其余的地方都建立起了堆的有序性。然后對根結(jié)點(diǎn)調(diào)用percolateDown，以創(chuàng)建堆的有序性。事實(shí)上并不一定需要遞歸。如果我們以逆向?qū)哟蔚拇涡驅(qū)Y(jié)點(diǎn)調(diào)用percolateDown，那么在percolateDown（i）被處理時(shí)，所有結(jié)點(diǎn)i的子孫都已經(jīng)調(diào)用過percolateDown。注意，不需要對葉結(jié)點(diǎn)執(zhí)行percolateDown。因此，我們是從編號(hào)最大的非葉結(jié)點(diǎn)開始。22例如，給出的數(shù)據(jù)初值為40，20，60，15，30，25，10，35，45，50，55，構(gòu)造一個(gè)最小化堆4035156010302025455055首先，將他看成是一棵完全二叉樹，然后把他調(diào)整成一個(gè)堆23403515601030202545505530和15沒有違反堆的有序性，接著調(diào)整604035151060302025455055調(diào)整204035201060301525455055調(diào)整40103520256030154045505524建堆總結(jié)自下往上調(diào)整每一個(gè)子堆在調(diào)整每個(gè)堆時(shí)，假設(shè)除根以外，所有節(jié)點(diǎn)滿足堆的定義根結(jié)點(diǎn)的調(diào)整是一個(gè)自上往下的過程：根和他的兒子比較，是否按足堆的定義。如不滿足，找一個(gè)大的兒子與他交換。但此時(shí)該兒子的子堆的有序性可能遭到破壞。再調(diào)整他的兒子、孫子…直到調(diào)整到葉結(jié)點(diǎn)為止。25建堆

template<classType>voidpriorityQueue<Type>::buildHeap(){for(inti=currentSize/2;i>0;i--)percolateDown(i);}

26帶有初始數(shù)據(jù)的構(gòu)造函數(shù)的實(shí)現(xiàn)template<classType>priorityQueue<Type>::priorityQueue(constType*items,intsize):maxSize(size+10),currentSize(size){array=newType[maxSize];for(inti=0;i<size;i++)array[i+1]=items[i];buildHeap();}27建堆的時(shí)間代價(jià)分析

建堆的時(shí)間是O(N)的。高度為h的節(jié)點(diǎn)（葉節(jié)點(diǎn)為0），在percolateDown中交換的最大次數(shù)是h。建堆的時(shí)間是所有節(jié)點(diǎn)的高度和。直觀上看，因?yàn)橐话氲慕Y(jié)點(diǎn)是葉子，它們的高度為0，而另外四分之一的結(jié)點(diǎn)高度為1，因此可以期望得到一個(gè)比O(NlogN)小的數(shù)。28定理：對于一棵高度為H，包含了N=2H+1-1個(gè)結(jié)點(diǎn)的滿二叉樹，結(jié)點(diǎn)的高度和為N–H–1證明：高度為h的結(jié)點(diǎn)有一個(gè)，高度為h-1的結(jié)點(diǎn)有2個(gè)，高度為h-2的結(jié)點(diǎn)有22個(gè)，高度為h-i的節(jié)點(diǎn)有2i個(gè)。因此，所有節(jié)點(diǎn)的高度和為：29第6章優(yōu)先級(jí)隊(duì)列基本的優(yōu)先級(jí)隊(duì)列二叉堆D堆歸并優(yōu)先級(jí)隊(duì)列STL中的優(yōu)先級(jí)隊(duì)列排隊(duì)系統(tǒng)的模擬30D-堆每個(gè)節(jié)點(diǎn)有k個(gè)兒子，這樣生成的堆比較矮。插入：O(logdN)刪除：需要在d個(gè)元素中找出最小的，時(shí)間復(fù)雜度為：O(dlogdN)優(yōu)點(diǎn)：插入快缺點(diǎn)：運(yùn)行時(shí)間長。因?yàn)樵诙娑阎械某?或除2操作可以用移位來實(shí)現(xiàn)，速度快。用途：插入比刪除多的隊(duì)列隊(duì)列太大，內(nèi)存放不下，要放在外存的時(shí)候31第6章優(yōu)先級(jí)隊(duì)列基本的優(yōu)先級(jí)隊(duì)列二叉堆D堆歸并優(yōu)先級(jí)隊(duì)列STL中的優(yōu)先級(jí)隊(duì)列排隊(duì)系統(tǒng)的模擬32歸并優(yōu)先級(jí)隊(duì)列左堆斜堆貝努里堆二叉堆能有效地支持優(yōu)先級(jí)隊(duì)列的入隊(duì)和出隊(duì)操作，但不能有效地支持兩個(gè)優(yōu)先級(jí)隊(duì)列的歸并。能有效地支持優(yōu)先級(jí)隊(duì)列歸并的數(shù)據(jù)結(jié)構(gòu)有左堆、斜堆和貝努里堆等33左堆滿足堆的有序性和結(jié)構(gòu)性，但平衡稍弱一些的堆定義：空路徑長度(npl)Npl(x)為x到不滿兩個(gè)孩子的節(jié)點(diǎn)的最短路徑。具有0個(gè)或一個(gè)孩子的節(jié)點(diǎn)的npl為0，npl(NULL)=-1左堆：對每個(gè)節(jié)點(diǎn)x，左孩子的npl不小于右孩子的npl顯然，左堆是向左傾斜的堆。341010001110000左堆非左堆35左堆的主要操作—?dú)w并采用遞歸的方法將根節(jié)點(diǎn)稍大的堆與另一個(gè)堆的右子樹歸并如產(chǎn)生的堆違反了左堆的定義，則交換左右子樹遞歸的終止條件：當(dāng)某個(gè)堆為空時(shí)，另一個(gè)堆就是歸并的結(jié)果3638102114232617H167121824331837H27378171826H2與H1的右子堆歸并12182433637左堆的入隊(duì)和出隊(duì)操作入隊(duì)可以看成是歸并的特例。將入隊(duì)元素看成是指有一個(gè)元素的左堆，歸并兩個(gè)左堆就形成了最終的結(jié)果。出隊(duì)操作的實(shí)現(xiàn)也很簡單。刪除了根結(jié)點(diǎn)后，這個(gè)堆就分裂成兩個(gè)堆。把這兩個(gè)堆重新歸并起來就是原始的隊(duì)列中執(zhí)行出隊(duì)運(yùn)算后的結(jié)果。38歸并優(yōu)先級(jí)隊(duì)列左堆斜堆貝努里堆二叉堆能有效地支持優(yōu)先級(jí)隊(duì)列的入隊(duì)和出隊(duì)操作，但不能有效地支持兩個(gè)優(yōu)先級(jí)隊(duì)列的歸并。能有效地支持優(yōu)先級(jí)隊(duì)列歸并的數(shù)據(jù)結(jié)構(gòu)有左堆、斜堆和貝努里堆等39斜堆斜堆是自調(diào)整的左堆。它滿足堆的有序性，但不滿足堆的結(jié)構(gòu)性。不需要維護(hù)npl。因此，右路徑可以任意長。最壞的時(shí)間復(fù)雜性O(shè)(N)，但對M個(gè)連續(xù)的操作，最壞的運(yùn)行時(shí)間是O(MlogN)。因此，每個(gè)操作由均攤的O(logN)的時(shí)間復(fù)雜度。它的操作比左堆簡單。40斜堆的歸并類似于左堆，只是在左堆中，歸并后左右子堆的交換是有條件的；而在斜堆中，是無條件的，必須交換。僅有一種例外情況：右路徑上所有節(jié)點(diǎn)中的最大者不需要交換它的孩子。4138102114232617H167121824331837H27378171826H2與H1的右子堆歸并12182433642斜堆的優(yōu)點(diǎn)不需要保存npl不需要維護(hù)npl不需要測試npl以決定是否要交換左右子堆43歸并優(yōu)先級(jí)隊(duì)列左堆斜堆貝努里堆二叉堆能有效地支持優(yōu)先級(jí)隊(duì)列的入隊(duì)和出隊(duì)操作，但不能有效地支持兩個(gè)優(yōu)先級(jí)隊(duì)列的歸并。能有效地支持優(yōu)先級(jí)隊(duì)列歸并的數(shù)據(jù)結(jié)構(gòu)有左堆、斜堆和貝努里堆等44貝努里隊(duì)列貝努里堆支持插入、刪除和歸并操作。最壞情況下的時(shí)間復(fù)雜性是O(N)，但平均的插入時(shí)間是一個(gè)常量。貝努里樹：高度為0的貝努里樹是單個(gè)節(jié)點(diǎn)，高度為k的貝努里樹Bk是將一棵Bk-1加到另一棵Bk-1的根上形成的。貝努里樹滿足堆的有序性45B0B1B2B346貝努里樹Bk的特性Bk有2k個(gè)節(jié)點(diǎn)第d層的節(jié)點(diǎn)數(shù)是貝努里系數(shù)47優(yōu)先級(jí)隊(duì)列的表示把優(yōu)先級(jí)隊(duì)列表示為貝努里樹的集合。每個(gè)高度至多有一棵貝努里樹。這樣，對于給定的元素個(gè)數(shù)，這個(gè)集合是唯一的，即元素個(gè)數(shù)的二進(jìn)制表示。如13個(gè)元素，可表示為1101。即該集合由B3、B2和B0組成48六個(gè)元素的貝努里隊(duì)列：16181221246514262351246513七個(gè)元素的貝努里隊(duì)列：49貝努里隊(duì)列的操作歸并入隊(duì)出隊(duì)50歸并操作由低到高依次歸并兩個(gè)優(yōu)先級(jí)隊(duì)列中高度相同的樹。如果由于前一次歸并而出現(xiàn)三棵高度相同的樹時(shí)，留下一棵，歸并其余兩棵。高度相同的樹的歸并：將根節(jié)點(diǎn)大的作為根節(jié)點(diǎn)小的樹的子樹。歸并的時(shí)間效益：N個(gè)元素的隊(duì)列有l(wèi)ogN棵樹，因此最壞情況為O(logN)。51歸并以下兩個(gè)隊(duì)列：14262351246513161812212465H1H2歸并B0：由于只有H2有B0，所以無需歸并歸并B1：形成以下的樹14261618現(xiàn)在有三棵B2，留下一棵，歸并其余兩棵52最后的隊(duì)列：1323512465122124651426161853貝努里隊(duì)列的操作歸并入隊(duì)出隊(duì)54插入插入是歸并的特例為被插入節(jié)點(diǎn)形成一棵單節(jié)點(diǎn)的樹組成的集合，歸并兩個(gè)集合時(shí)間效益：最壞情況為O(logN)，相當(dāng)于二進(jìn)制加法中的加1，但每次都有進(jìn)位的情況。一般進(jìn)位進(jìn)到中間的某一位會(huì)終止。即當(dāng)原先集合中缺少Bi時(shí)，則歸并i次，由于每棵樹的出現(xiàn)是等概率的，因此平均歸并兩次就能結(jié)束。55貝努里隊(duì)列的操作歸并入隊(duì)出隊(duì)56刪除找出具有最小根值的樹T將T從原先的集合中刪掉在T中刪除根節(jié)點(diǎn)歸并T與原先的集合57在以下的隊(duì)列中刪除最小元素：13235124651221246514261618最小元素出現(xiàn)在B3中，刪除最小元素12，形成下列森林：2124651426161858歸并兩個(gè)森林：23512465132124651426161859貝努里隊(duì)列的存儲(chǔ)每棵樹看成是有序樹，采用標(biāo)準(zhǔn)的樹的存儲(chǔ)方式—孩子兄弟鏈的表示法整個(gè)森林表示成一個(gè)指向樹根的指針的線性表6013235124651221246514261618如下的貝努里隊(duì)列可表示成：1323245165122124651426161861貝努里隊(duì)列的時(shí)間性能歸并：N個(gè)元素的隊(duì)列至多有l(wèi)ogN棵樹，每兩棵樹的歸并只需要常量的時(shí)間。因此最壞情況的時(shí)間復(fù)雜度為O(logN)。但可以證明平均情況的時(shí)間復(fù)雜度是常量的。入隊(duì)操作的平均時(shí)間復(fù)雜度是O（1）的出隊(duì)操作：首先在隊(duì)列中找出根結(jié)點(diǎn)值最小的樹。這需要花費(fèi)O（logN）的時(shí)間。然后又要?dú)w并兩個(gè)優(yōu)先級(jí)隊(duì)列，又需要O（logN）的時(shí)間。所以刪除操作的時(shí)間復(fù)雜度是O（logN）的62第6章優(yōu)先級(jí)隊(duì)列基本的優(yōu)先級(jí)隊(duì)列二叉堆D堆歸并優(yōu)先級(jí)隊(duì)列STL中的優(yōu)先級(jí)隊(duì)列排隊(duì)系統(tǒng)的模擬63STL中的優(yōu)先級(jí)隊(duì)列頭文件：queue類模版：priority_queue實(shí)現(xiàn)方式：二叉堆主要成員：Voidpush(constObject&x)ConstObject&top()constVoidpop()Boolempty()Voidclear()64使用實(shí)例#include<iostream>#include<queue>usingnamespacestd;intmain(){priority_queue<int>q;q.push(10);q.push(1);q.push(5);q.push(8);q.push(0);q.push(4);q.push(9);q.push(7);q.push(3);q.push(6);q.push(2);while(!q.empty()){cout<<q.top()<<"";q.pop();}return0;}65第6章優(yōu)先級(jí)隊(duì)列基本的優(yōu)先級(jí)隊(duì)列二叉堆D堆歸并優(yōu)先級(jí)隊(duì)列STL中的優(yōu)先級(jí)隊(duì)列排隊(duì)系統(tǒng)的模擬66單服務(wù)臺(tái)的排隊(duì)系統(tǒng)在單服務(wù)臺(tái)系統(tǒng)中，先到達(dá)的顧客先獲得服務(wù)，也肯定先離開事件處理的次序是：顧客1到達(dá)、顧客1離開、顧客2到達(dá)、顧客2離開、……、顧客n到達(dá)、顧客n離開只需要一個(gè)普通隊(duì)列保存顧客到達(dá)信息67多服務(wù)臺(tái)的排隊(duì)系統(tǒng)在多服務(wù)臺(tái)系統(tǒng)中，先到達(dá)的顧客先獲得服務(wù)，但后獲得服務(wù)的顧客可能先離開；事件處理的次序可能是：顧客1到達(dá)、顧客2到達(dá)、顧客2離開、顧客3到達(dá)、顧客1離開、顧客3離開……、顧客n到達(dá)、顧客n離開、……發(fā)生時(shí)間早的事件先處理，發(fā)生時(shí)間晚的事件后處理。因而需要一個(gè)優(yōu)先級(jí)隊(duì)列存放事件。事件的優(yōu)先級(jí)就是發(fā)生的時(shí)間68模擬過程模擬開始時(shí)，產(chǎn)生所有的到達(dá)事件，存入優(yōu)先級(jí)隊(duì)列。模擬器開始處理事件：從隊(duì)列中取出一個(gè)事件。這是第一個(gè)顧客的到達(dá)事件。生成所需的服務(wù)時(shí)間。當(dāng)前時(shí)間加上這個(gè)服務(wù)時(shí)間就是這個(gè)顧客的離開時(shí)間。生成一個(gè)在這個(gè)時(shí)候離開的事件，插入到事件隊(duì)列。同樣模擬器從隊(duì)列中取出的事件也可能是離開事件，這時(shí)只要將這個(gè)離開事件從隊(duì)列中刪去，為他服務(wù)的服務(wù)臺(tái)變成了空閑狀態(tài)，可以繼續(xù)為別的顧客服務(wù)。69產(chǎn)生CustomNum個(gè)顧客的到達(dá)事件，按時(shí)間的大小存入事件隊(duì)列；置等待隊(duì)列為空；置所有柜臺(tái)為空閑；設(shè)置等待時(shí)間為0；多服務(wù)臺(tái)的排隊(duì)系統(tǒng)過程70While（事件隊(duì)列非空）{

隊(duì)頭元素出隊(duì)；設(shè)置當(dāng)前時(shí)間為該事件發(fā)生的時(shí)間；

switch(事件類型）

{case到達(dá)：if(柜臺(tái)有空){柜臺(tái)數(shù)減1；生成所需的服務(wù)時(shí)間；修改事件類型為“離開”設(shè)置事件發(fā)生時(shí)間為當(dāng)前時(shí)間加上服務(wù)時(shí)間；重新存入事件隊(duì)列；}else將該事件存入等待隊(duì)列；

case離開：if（等待隊(duì)列非空）

{隊(duì)頭元素出隊(duì)；統(tǒng)計(jì)該顧客的等待時(shí)間；生成所需的服務(wù)時(shí)間；修改事件類型為“離開”設(shè)置事件發(fā)生時(shí)間為當(dāng)前時(shí)間加上服務(wù)時(shí)間；存入事件隊(duì)列；}else空閑柜臺(tái)數(shù)加1；

}}計(jì)算平均等待時(shí)間；返回；}71模擬類設(shè)計(jì)一個(gè)模擬類，告訴它顧客到達(dá)時(shí)間間隔的分布、服務(wù)時(shí)間的分布、模擬的柜臺(tái)數(shù)以及想要模擬多少個(gè)顧客。能提供在本次服務(wù)中顧客的平均等待時(shí)間是多少。因此這個(gè)類應(yīng)該有兩個(gè)公有函數(shù)：構(gòu)造函數(shù)接受用戶輸入的參數(shù)，另外一個(gè)就是執(zhí)行模擬并最終給出平均等待時(shí)間的函數(shù)avgWaitTime。這個(gè)類要保存的數(shù)據(jù)就是模擬的參數(shù)。72模擬類的定義classsimulator{ intnoOfServer;//服務(wù)臺(tái)個(gè)數(shù)

intarrivalLow;//到達(dá)間隔時(shí)間的下界

intarrivalHigh;//到達(dá)間隔時(shí)間的上界

intserviceTimeLow;//服務(wù)間隔時(shí)間的下界

intserviceTimeHigh;//服務(wù)間隔時(shí)間的上界

intcustomNum;//模擬的顧客數(shù)

structeventT {inttime;//事件發(fā)生時(shí)間

inttype;//事件類型。0為到達(dá)，1為離開

booloperator<(consteventT&e)const{returntime<e.time;} };public: simulator(); intavgWaitTime();};73構(gòu)造函數(shù)的實(shí)現(xiàn)simulator::simulator(){cout<<"請輸入柜臺(tái)數(shù)："; cin>>noOfServer;cout<<“請輸入到達(dá)時(shí)間間隔的上下界（最小間隔時(shí)間最大間隔時(shí)間）：";cin>>arrivalLow>>arrivalHigh;cout<<“請輸入服務(wù)時(shí)間的上下界（服務(wù)時(shí)間下界服務(wù)時(shí)間上界）："; cin>>serviceTimeLow>>serviceTimeHigh; cout<<"請輸入模擬的顧客數(shù)：";cin>>customNum;srand(time(NULL));}74avgWaitTime()intsimulator::avgWaitTime(){intserverBusy=0;//正在工作的服務(wù)臺(tái)數(shù)

intcurrentTime;//記錄模擬過程中的時(shí)間

inttotalWaitTime=0;//模擬過程中所有顧客的等待時(shí)間的總和

linkQueue<eventT>waitQueue;//顧客等待隊(duì)列

priorityQueue<eventT>eventQueue;//事件隊(duì)列

eventTcurrentEvent;

75//生成初始的事件隊(duì)列

inti;currentEvent.time=0;currentEvent.type=0;for(i=0;i<customNum;++i){currentEvent.time+=arrivalLow+(arrivalHigh-arrivalLow+1)*rand()/(RAND_MAX+1);eventQueue.enQueue(currentEvent);}76//模擬過程

while(!eventQueue.isEmpty()){currentEvent=eventQueue.deQueue();currentTime=currentEvent.time;switch(currentEvent.ty