第六章 優(yōu)先級隊列

1、數(shù)據(jù)結(jié)構(gòu)Data Structure,第六章 優(yōu)先級隊列,第六章 優(yōu)先級隊列,基本的優(yōu)先級隊列 二叉堆 D堆 歸并優(yōu)先級隊列 STL中的優(yōu)先級隊列 排隊系統(tǒng)的模擬,基本的優(yōu)先級隊列,結(jié)點之間的關(guān)系是由結(jié)點的優(yōu)先級決定的，而不是由入隊的先后次序決定。優(yōu)先級高的先出隊，優(yōu)先級低的后出隊。這樣的隊列稱為優(yōu)先級隊列。,Priority queue,Collections. Insert and delete items. Which

2、 item to delete?Stack. Remove the item most recently added.Queue. Remove the item least recently added.Randomized queue. Remove a random item.Priority queue. Remove the largest (or smallest) item.,Priority queue appl

3、ications,Event-driven simulation. [customers in a line, colliding particles]Numerical computation. [reducing round off error]Data compression. [Huffman codes]Graph searching. [Dijkstra's algorithm, Prim'

4、s algorithm]Number theory. [sum of powers]Artificial intelligence. [A* search]Statistics. [maintain largest M values in a sequence]Operating systems. [load balancing, interrupt handling]Discrete optimization

5、. [bin packing, scheduling]Spam filtering. [Bayesian spam filter],Challenge. Find the largest M files in N itemsConstraint. Not enough memory to store N items,優(yōu)先級隊列的簡單實現(xiàn),利用現(xiàn)有的隊列結(jié)構(gòu)。有兩種方法可以處理優(yōu)先級 入隊時，按照優(yōu)先級在隊列中尋找合適的位置，

6、 將新入隊的元素插入在此位置。出隊操作的實現(xiàn)保持不變。入隊操作的時間復(fù)雜度是O （N），出隊操作的時間復(fù)雜度是O（1）。 入隊操作的實現(xiàn)保持不變，將新入隊的元素放在 隊列尾。但出隊時，在整個隊列中查找優(yōu)先級最高的元素，讓它出隊。入隊操作的時間復(fù)雜度是O （1），出隊操作的時間復(fù)雜度是O（N）。,第六章 優(yōu)先級隊列,基本的優(yōu)先級隊列 基于樹形結(jié)構(gòu)的優(yōu)先級隊列——二叉堆 D堆 歸并優(yōu)先級隊列 STL中的優(yōu)先級隊列 排隊系

7、統(tǒng)的模擬,,,2h-1,2h ? 1,? Array Representation : BT [ n + 1 ] ( BT [ 0 ] is not used),完全二叉樹,定義：A binary tree with n nodes and height h is complete iff its nodes correspond to the nodes numbered from 1 to n in the perfect

8、 binary tree of height h.,【定理】If a complete binary tree with n nodes is represented sequentially, then for any node with index i, 1 ? i ? n, we have:,自然界的完全二叉樹,二叉堆,堆是一棵完全二叉樹，且滿足下述關(guān)系之一 ki ≤ k2i 且 ki ≤ k2i+1 (i=1,2,… , ?

9、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} 是最大化堆,最大化堆,最小化堆,二叉堆的特性,結(jié)構(gòu)性：符合完全二叉樹的結(jié)構(gòu) 有序性：滿足父節(jié)點小于子節(jié)點

10、（最小化堆）或父節(jié)點大于子節(jié)點（最大化堆） 以下的討論都以最小化堆為例,二叉堆的存儲,可以采用順序存儲二叉堆的有序性可以很容易地通過下標(biāo)來反映,基于二叉堆的優(yōu)先級隊列,如果數(shù)值越小，優(yōu)先級越高，則可以用一個最小化堆存儲優(yōu)先級隊列 在最小化堆中，最小元素是根元素，而根結(jié)點永遠(yuǎn)存放在數(shù)組的下標(biāo)為1的元素中。 獲取隊頭元素的操作就是返回下標(biāo)為1的數(shù)組元素值 出隊操作就是刪除下標(biāo)為1的數(shù)組元素中的值 入隊操作就是在數(shù)組的末尾添加一個

11、元素，但添加后要調(diào)整元素的位置，以保持堆的有序性,優(yōu)先級隊列類的定義,template class priorityQueue {private: int currentSize; //隊列中元素個數(shù) Type *array; //數(shù)組的起始地址 int maxSize; //數(shù)組的規(guī)模 void doubleSpace( ); void buildHeap( );

12、 void percolateDown( int hole ); //向下過濾,public: priorityQueue( int capacity = 100 ) //創(chuàng)建一個空優(yōu)先級隊列 { array = new Type[capacity]; maxSize = capacity; currentSize = 0;} priority

13、Queue( const Type data[], int size ); //從一組給定的數(shù)據(jù)創(chuàng)建一個優(yōu)先級隊列 ~priorityQueue() { delete [] array; } bool isEmpty( ) const { return currentSize == 0; } void enQueue( const Type & x ); Type deQueue( );

14、 Type getHead( ) { return array[1]; } };,enQueue（x）,enQueue操作是在堆中插入一個新元素 堆的插入是在具有最大序號的元素之后插入新的元素或結(jié)點，否則將違反堆的結(jié)構(gòu)性。 如果新元素放入后，沒有違反堆的有序性，那么操作結(jié)束。否則，讓該節(jié)點向父節(jié)點移動，直到滿足有序性或到達根節(jié)點。 新節(jié)點的向上移動稱為向上過濾(percolate up),?在如下的堆中插入元素的過程：,T

15、he only possible position for a new node since a heap must be a complete binary tree.,Case 1 : new_item = 21,21,Case 2 : new_item = 17,17,17,20,Case 3 : new_item = 9,9,9,10,enQueue過程,template void priorityQueue::

16、enQueue( const Type & x ) { if( currentSize == maxSize - 1 ) doubleSpace(); // 向上過濾 int hole = ++currentSize; for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 ) //在x大于空結(jié)點的父結(jié)點或已過濾到根時終止循環(huán)

17、 array[ hole ] = array[ hole / 2 ]; array[ hole ] = x; },enQueue的時間效率,最壞情況是對數(shù)的 O(logN)平均情況，過濾會提前結(jié)束。有資料表明，平均是2.6次比較，因此元素平均上移1.6層。,DeQueue 操作,當(dāng)最小元素被刪除時，在根上出現(xiàn)了一個空結(jié)點。堆的大小比以前小1，堆的結(jié)構(gòu)性告訴我們，最后一個結(jié)點應(yīng)該刪掉。 如果最后一項可以放在此空結(jié)點中

18、，就把它放進去。然而，這通常是不可能的。 我們必須玩與插入操作相同的游戲：把某些項放 入空結(jié)點，然后移動空結(jié)點。僅有的區(qū)別在于： 對DeQueue操作，空結(jié)點是往下移動。,向下過濾過程,找到空結(jié)點的一個較小的子結(jié)點，如果該兒子的值小于我們要放入的項，則把該兒子放入空結(jié)點，把空結(jié)點往下推一層，重復(fù)這個動作，直到該項能被放入,? 刪除最小元素,,,The node which must beremoved to keep acomp

19、lete binary tree.,,,? move 18 up to the root,,18,? find the smaller child of 18,,18,12,,18,15,Ah! That’s simple --we only have to deletethe root node ...,And re-arrange the rest of the tree so that it’s still a mi

20、n heap.,T (N) = O ( log N ),deQueue(),template Type priorityQueue::deQueue() { Type minItem; minItem = array[ 1 ]; array[ 1 ] = array[ currentSize-- ]; //將最后一個元素挪到根節(jié)點 percolateDown( 1 ); //向下過濾 return mi

21、nItem; },向下過濾,template void priorityQueue::percolateDown( int hole ) { int child; Type tmp = array[ hole ]; for( ; hole * 2 <= currentSize; hole = child ) //每次循環(huán)下移一層 { child = hole * 2; //child指向左兒子

22、 if( child != currentSize && array[ child + 1 ] < array[ child ] ) child++; //如果右兒子存在且小于左兒子，將child指向右兒子 if( array[ child ] < tmp ) array[ hole ] = array[ child ]; //空結(jié)點小于左（右）孩子，

23、空結(jié)點下移 else break; //空結(jié)點位于合適位置，跳出循環(huán) } array[ hole ] = tmp; },deQueue操作的性能,因為樹有對數(shù)的深度，在最壞情況下， deQueue是一個對數(shù)時間的操作O(logN)。 根據(jù)堆的有序性，堆中最后一個結(jié)點的值一般都是比較大的。因此，向下過濾很少有提前一或二層結(jié)束的，所以deQueue操作平均也是對數(shù)時間。,建堆,可以看成N次連續(xù)插

24、入，其時間應(yīng)該是在O(NlogN) 時間內(nèi)完成。 事實上，在構(gòu)造過程中，我們并不關(guān)心每個元素加 入后堆的狀態(tài)，我們關(guān)心的是N個元素全部加入后的最后狀態(tài)，最后的狀態(tài)是要保證堆的有序性。至于中間過程中的有序性是否成立并不重要。 有了這個前提后，我們能將構(gòu)造堆的時間復(fù)雜度降到O（N）,建堆過程的遞歸實現(xiàn),利用堆的遞歸定義 如果函數(shù)buildHeap可以將一棵完全二叉樹 調(diào)整為一個堆 ，那么，只要對左子堆和右 子堆遞歸調(diào)用buildHea

25、p。至此，我們能保 證除了根結(jié)點外，其余的地方都建立起了堆的有序性。然后對根結(jié)點調(diào)用percolateDown，以創(chuàng)建堆的有序性。,建堆過程的非遞歸實現(xiàn),如果我們以逆向?qū)哟蔚拇涡驅(qū)Y(jié)點調(diào)用 percolateDown，那么在percolateDown（i） 被處理時，所有結(jié)點i的子孫都已經(jīng)調(diào)用過 percolateDown。 注意，不需要對葉結(jié)點執(zhí)行percolateDown。 因此，我們是從編號最大的非葉結(jié)點開始。,template

26、 void priorityQueue::buildHeap( ) { for ( int i = currentSize/2; i > 0; i-- ) percolateDown( i ); }currentSize/2: 編號最大的非葉結(jié)點,帶有初始數(shù)據(jù)的構(gòu)造函數(shù)的實現(xiàn),template priorityQueue::priorityQueue( const Type *items, i

27、nt size ) : maxSize(size + 10 ), currentSize(size) { array = new Type[maxSize]; for( int i = 0; i < size; i++ ) array[ i + 1 ] = items[ i ]; buildHeap( ); },10,40,建堆過程,例如，給出的數(shù)據(jù)初值為40，20，60，15，30，2

28、5，10，35，45，50，55，構(gòu)造一個最小化堆,25,40,60,10,35,,60,10,30,,,,,25,,,,45,,50,,55,,15,20,20,15,由給出的數(shù)據(jù)構(gòu)造一棵完全二叉樹,對結(jié)點30執(zhí)行向下過濾,對結(jié)點15執(zhí)行向下過濾,對結(jié)點60執(zhí)行向下過濾,對結(jié)點20執(zhí)行向下過濾,對結(jié)點40執(zhí)行向下過濾,定理：對于一棵高度為h，包含了N = 2h+1 - 1個結(jié)點的滿二叉樹，結(jié)點的高度和為N – h – 1 證明：高度

29、為h的結(jié)點有一個，高度為h-1的結(jié)點有2個，高度為h-2的結(jié)點有22個，高度為h-i的節(jié)點有2i個。因此，所有節(jié)點的高度和為：,建堆的時間代價分析,建堆的時間是O(N)。 高度為h的節(jié)點（葉節(jié)點為0），在 percolateDown中交換的最大次數(shù)是h。 建堆的時間是所有節(jié)點的調(diào)整時所需交換 次數(shù)之和，即所有節(jié)點的高度之和 N – h – 1 。,第六章 優(yōu)先級隊列,基本的優(yōu)先級隊列 二叉堆 D堆 歸并優(yōu)先級隊列 STL中的

30、優(yōu)先級隊列 排隊系統(tǒng)的模擬,---- All nodes have d children,Question: Shall we make d as large as possible?,D-堆,D-堆,每個節(jié)點有d個兒子，這樣生成的堆比較矮。 插入：O(logdN) 刪除：向下過濾時，需要在d個兒子中找出最小的(O(d))，時間復(fù)雜度為：O(dlogdN) 優(yōu)點：插入快 缺點：刪除慢 用途： 插入比刪除多很多的應(yīng)用優(yōu)先

31、級隊列太大，內(nèi)存放不下，要放在外存的時候（減少內(nèi)外存的交換）,第六章 優(yōu)先級隊列,基本的優(yōu)先級隊列 二叉堆 D堆 歸并優(yōu)先級隊列 STL中的優(yōu)先級隊列 排隊系統(tǒng)的模擬,歸并優(yōu)先級隊列,二叉堆能有效地支持優(yōu)先級隊列的入隊和出隊操作，但不能有效地支持兩個優(yōu)先級隊列的歸并。能有效地支持優(yōu)先級隊列歸并的數(shù)據(jù)結(jié)構(gòu)有左堆 斜堆 貝努里堆,空路徑長度,空路徑長度(npl)：npl(x)為x到不滿兩個孩子的節(jié)點的最短路徑。具有0個或一個

32、孩子的節(jié)點的npl為 0，npl(NULL) = -1,左堆,左堆：對每個節(jié)點x，左孩子的npl不小于右 孩子的npl 顯然，左堆是向左傾斜的堆。滿足堆的有序性，但平衡稍弱一些的堆,?,左堆的主要操作—歸并,采用遞歸的方法 將根節(jié)點稍大的堆與另一個堆的右子樹歸并 如產(chǎn)生的堆違反了左堆的定義，則交換左右子樹 遞歸的終止條件：當(dāng)某個堆為空時，另一個堆就是歸并的結(jié)果,H1,H2,3,8,10,21,14,,,,,,23,26,17,

33、,,6,7,12,18,24,,,,,,33,18,37,,,18,,8,26,17,,,左堆的入隊和出隊操作,入隊可以看成是歸并的特例。將入隊元素看成是指有一個元素的左堆，歸并兩個左堆就形成了最終的結(jié)果。 出隊操作的實現(xiàn)也很簡單。刪除了根結(jié)點 后，這個堆就分裂成兩個堆。把這兩個堆重新歸并起來就是原始的隊列中執(zhí)行出隊運算后的結(jié)果。,斜堆,斜堆是自調(diào)整的左堆。它滿足堆的有序性，但不滿足堆的結(jié)構(gòu)性。不需要維護npl。因此，右路徑可以任意長

34、。 最壞的時間復(fù)雜性O(shè)(N)，但對M個連續(xù)的操作，最壞的運行時間是O(MlogN)。因此，每個操作由均攤的O(logN)的時間復(fù)雜度。 它的操作比左堆簡單。,斜堆的歸并,類似于左堆，只是在左堆中，歸并后左 右子堆的交換是有條件的；而在斜堆中，是無條件的，必須交換。僅有一種例外情況：右路徑上所有節(jié)點中的最大者不需要交換它的孩子。,H1,H2,3,8,10,21,14,,,,,,23,26,17,,,6,7,12,18,24,,,,,,

35、33,18,37,,,18,,8,26,17,,,斜堆的優(yōu)點,不需要保存npl 不需要維護npl 不需要測試npl以決定是否要交換左右子堆,貝努里隊列,貝努里隊列支持插入、刪除和歸并操作。 最壞情況下的時間復(fù)雜性是O(logN)，但平均的插入時間是一個常量。 貝努里隊列表示為一個貝努里樹的集合。,貝努里樹,貝努里樹是一棵普通的樹，不是二叉樹。 高度為0的貝努里樹是單個節(jié)點，高度為k的貝努里樹Bk是將一棵Bk-1加到另一棵Bk-1

36、的根上形成的。 貝努里樹滿足堆的有序性,,B0,B1,B2,貝努里樹Bk的特性,Bk有2k個節(jié)點 第d層的節(jié)點數(shù)是貝努里系數(shù),優(yōu)先級隊列的表示,把優(yōu)先級隊列表示為貝努里樹的集合。 每個高度至多有一棵貝努里樹。這樣，對于給定的元素個數(shù)，這個集合是唯一的，即元素個數(shù)的二進制表示中的1的個數(shù)。 如13個元素，可表示為1101。即該集合由B3、B2和B0組成,六個元素的貝努里隊列：,七個元素的貝努里隊列：,貝努里隊列的操作,歸并 入隊

37、出隊,歸并操作,由低到高依次歸并兩個優(yōu)先級隊列中高度 相同的樹。如果由于前一次歸并而出現(xiàn)三 棵高度相同的樹時，留下一棵，歸并其余 兩棵。 高度相同的樹的歸并：將根節(jié)點大的作為 根節(jié)點小的樹的子樹。 歸并的時間效益：N個元素的隊列有l(wèi)ogN 棵樹，因此最壞情況為O(logN)。,歸并以下兩個隊列：,14,26,,23,51,,24,65,,,13,16,18,,12,21,,24,65,,,H1,H2,,,歸并B0：由于只有H2有B

38、0，所以無需歸并歸并B1：形成以下的樹,14,26,,16,18,,,現(xiàn)在有三棵B2，留下一棵，歸并其余兩棵,最后的隊列：,插入,插入是歸并的特例 為被插入節(jié)點形成一棵單節(jié)點的樹組成的集合， 歸并兩個集合 時間效益：最壞情況為O(logN)，相當(dāng)于二進制加法中的加1，但每次都有進位的情況。一般進 位進到中間的某一位會終止。即當(dāng)原先集合中缺 少Bi時，則歸并i次，由于每棵樹的出現(xiàn)是等概率的，因此平均歸并兩次就能結(jié)束。,刪除,找出具有

39、最小根值的樹T 將T從原先的集合中刪掉 在T中刪除根節(jié)點 歸并T與原先的集合,在以下的隊列中刪除最小元素：,13,12,21,,24,65,,,14,26,,16,18,,,,最小元素出現(xiàn)在B3中，刪除最小元素12，形成下列森林：,歸并兩個森林：,13,21,,24,65,,,14,26,,16,18,,,,貝努里隊列的存儲,每棵樹看成是有序樹，采用標(biāo)準(zhǔn)的樹的存儲方式—孩子兄弟鏈的表示法整個森林表示成一個指向樹根的指針的線性表,

40、13,12,21,,24,65,,,14,26,,16,18,,,,如下的貝努里隊列可表示成：,13,,23,24,51,65,,12,21,24,65,14,26,16,18,,,,,,,,,,,,貝努里隊列的時間性能,歸并：N個元素的隊列至多有l(wèi)ogN棵樹，每兩棵樹的歸并只需要常量的時間。因此最壞情況的時間復(fù)雜度為O(logN)。但可以證明平均情況的時間復(fù)雜度是常量的。 入隊操作的平均時間復(fù)雜度是O（1）的 出隊操作：首先在隊列

41、中找出根結(jié)點值最小的樹。這需要花費O（logN）的時間。然后又要歸并兩個優(yōu)先級隊列，又需要O（logN）的時間。所以 刪除操作的時間復(fù)雜度是O（logN）的,第六章 優(yōu)先級隊列,基本的優(yōu)先級隊列 二叉堆 D堆 歸并優(yōu)先級隊列 STL中的優(yōu)先級隊列 排隊系統(tǒng)的模擬,STL中的優(yōu)先級隊列,頭文件：queue 類模版：priority_queue 實現(xiàn)方式：二叉堆 主要成員： Void push( const Object

42、&x) Const Object &top() const Void pop() Bool empty() Void clear(),使用實例,#include #include using namespace std; int main() { priority_queue q; //最大化堆，第2、3參數(shù)可缺省 q.push(10); q.push(1); q.push(5); q.pus

43、h(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 , greater> q; //最小化堆,第六章 優(yōu)先級隊列,基本的優(yōu)先級隊列 二叉堆 D堆 歸并優(yōu)先級隊列 STL中的優(yōu)先級隊列 排隊系統(tǒng)的模擬,單服務(wù)臺的排隊系統(tǒng),在單服務(wù)臺系統(tǒng)中

44、，先到達的顧客先獲得 服務(wù)，也肯定先離開。到達和離開的次序 是一致的。 事件處理的次序是：顧客1到達、顧客1離 開、顧客2到達、顧客2離開、……、顧客n 到達、顧客n離開 顧客離開順序和到達順序一致。只需要一個普通隊列保存顧客到達信息,多服務(wù)臺的排隊系統(tǒng),在多服務(wù)臺系統(tǒng)中，先到達的顧客先獲得服務(wù)，但后獲得服務(wù)的顧客可能先離開； 事件處理的次序可能是：顧客1到達、顧客2到達、 顧客2離開、顧客3到達、顧客1離開、顧客3離 開……、顧

45、客n到達、顧客n離開、…… 發(fā)生時間早的事件先處理，發(fā)生時間晚的事件后處理。因而需要一個優(yōu)先級隊列存放事件。事件的優(yōu)先級就是發(fā)生的時間,多服務(wù)臺的排隊系統(tǒng)模擬,產(chǎn)生CustomNum個顧客的到達事件，按時間的大小存入事件隊列； 置初值置等待隊列為空； 置所有柜臺為空閑； 設(shè)置等待時間為0；模擬器開始處理事件： 從隊列中取出一個事件。這是第一個顧客的到達事件。 生成所需的服務(wù)時間。當(dāng)前時間加上這個服務(wù)時間就是 這個顧客的離開

46、時間。生成一個在這個時候離開的事件，插入到事件隊列。 同樣模擬器從隊列中取出的事件也可能是離開事件，這 時只要將這個離開事件從隊列中刪去，為他服務(wù)的服務(wù)臺變成了空閑狀態(tài)，可以繼續(xù)為別的顧客服務(wù)。,模擬類的定義,class simulator{ int noOfServer; //服務(wù)臺個數(shù) int arrivalLow; //到達間隔時間的下界 int arrivalHigh; //到達間隔時間的上界 int serv

47、iceTimeLow; //服務(wù)間隔時間的下界 int serviceTimeHigh; //服務(wù)間隔時間的上界 int customNum; //模擬的顧客數(shù) struct eventT { int time; //事件發(fā)生時間 int type; //事件類型。0為到達，1為離開 bool operator<(const eventT &e) const {return tim

48、e < e.time;} } ; //設(shè)置隨機數(shù)種子 public: simulator(); //構(gòu)造函數(shù), 接受用戶輸入的參數(shù)int avgWaitTime(); //執(zhí)行模擬并最終給出平均等待時間};,構(gòu)造函數(shù)的實現(xiàn),simulator::simulator() { cout > noOfServer; cout > arrivalLow >> arrivalHigh;

49、cout > serviceTimeLow >> serviceTimeHigh; cout > customNum; srand(time(NULL)); //隨機數(shù)發(fā)生器的初始化},avgWaitTime(),int simulator::avgWaitTime() { int serverBusy = 0; // 正在工作的服務(wù)臺數(shù) int currentTime ; // 記

50、錄模擬過程中的時間 int totalWaitTime = 0; //模擬過程中所有顧客的等待時間的總和 linkQueue waitQueue; //顧客等待隊列 priorityQueue eventQueue; //事件隊列 eventT currentEvent; //當(dāng)前事件,,//產(chǎn)生customNum個顧客的到達事件，按到達時間大小入隊，生成初始的事件隊列 int i; curr

51、entEvent.time = 0; currentEvent.type = 0; for (i=0; i<customNum; ++i) { currentEvent.time += arrivalLow + (arrivalHigh -arrivalLow +1) * rand() / (RAND_MAX

52、+ 1); eventQueue.enQueue(currentEvent); },//模擬過程 while (!eventQueue.isEmpty()) //事件隊列非空 {currentEvent = eventQueue.deQueue(); //出隊 currentTime = currentEvent.time; //設(shè)置當(dāng)前時間為該事件發(fā)生的時間 switch(curr

53、entEvent.type) {case 0: 處理到達事件 break; case 1: 處理離開事件 } //switch結(jié)束 } //while結(jié)束 return totalWaitTime / customNum; },處理到達事件,if (serverBusy != noOfServer) //有空閑服務(wù)臺{ ++serverBusy; c

54、urrentEvent.time += serviceTimeLow + (serviceTimeHigh - serviceTimeLow +1) * rand() / (RAND_MAX + 1); //設(shè)置事件發(fā)生時間為當(dāng)前時間加上服務(wù)時間 currentEvent.type = 1; //修改事件類型為離開 eventQueue.enQu

55、eue(currentEvent); //重新放入事件隊列} else waitQueue.enQueue(currentEvent); //事件放入等待隊列,處理離開事件,if (!waitQueue.isEmpty()) //等待隊列非空{(diào) currentEvent = waitQueue.deQueue(); //出隊 totalWaitTime += currentTime - currentEvent.time;

56、//統(tǒng)計等待時間 currentEvent.time = currentTime + serviceTimeLow + (serviceTimeHigh - serviceTimeLow +1) * rand() / (RAND_MAX + 1); //設(shè)置事件發(fā)生時間為當(dāng)前時間加上服務(wù)時間 currentEvent.type = 1; //修改事件類型為離開 e

57、ventQueue.enQueue(currentEvent); //重新放入事件隊列} else --serverBusy; //空閑柜臺數(shù)加1,simulator類的使用,int main() { simulator sim; cout << "平均等待時間：" << sim.avgWaitTime() << endl; r

58、eturn 0; },某次執(zhí)行結(jié)果,請輸入柜臺數(shù)：4 請輸入到達時間間隔的上下界（最小間隔 時間 最大間隔時間）：0 2 請輸入服務(wù)時間的上下界（服務(wù)時間下界 服務(wù)時間上界）：2 7 請輸入模擬的顧客數(shù)：1000 平均等待時間：61,總結(jié),優(yōu)先級隊列是程序設(shè)計中常用的一個工具。 本章介紹了一種優(yōu)先級隊列的優(yōu)秀的實現(xiàn)方 法 —— 二叉堆。 還介紹了一些能夠?qū)崿F(xiàn)優(yōu)先級隊列歸并的堆的概念最后。介紹了優(yōu)先級隊列的一個重要應(yīng)用，即

59、多服務(wù)臺的排隊系統(tǒng)的模擬。,作業(yè),程序設(shè)計題：5、7、8題,Molecular dynamics simulation of hard discs,Goal. Simulate the motion of N moving particles that behave according to the laws of elastic collision.Hard disc model.Moving particles interact

60、 via elastic collisions with each other and walls.Each particle is a disc with known position, velocity, mass, and radius.No other forces.Significance. Relates macroscopic observables to microscopic dynamics.Maxwell

61、-Boltzmann: distribution of speeds as a function of temperature.Einstein: explain Brownian motion of pollen grains.,temperature, pressure,diffusion constant,motion of individualatoms and molecules,Time-driven simulati

62、on,Discretize time in quanta of size dt.Update the position of each particle after every dt units of time, and check for overlaps.If overlap, roll back the clock to the time of the collision, update the velocities of t

63、he colliding particles, and continue the simulation.,Time-driven simulation,Main drawbacks.~ N2/2 overlap checks per time quantum.Simulation is too slow if dt is very small.May miss collisions if dt is too large.(if

64、colliding particles fail to overlap when we are looking),Event-driven simulation,Change state only when something happens.Between collisions, particles move in straight-line trajectories.Focus only on times when collis

65、ions occur.Maintain priority queues (PQ) of collision events, prioritized by time.Remove the min = get next collision.Collision prediction. Given position, velocity, and radius of a particle, when will it collide next

66、 with a wall or another particle?Collision resolution. If collision occurs, update colliding particle(s) according to laws of elastic collisions.,Particle-wall collision,Collision prediction and resolution.Particle of

67、radius s at position (rx, ry).Particle moving in unit box with velocity (vx, vy).Will it collide with a vertical wall? If so, when?,Particle-particle collision prediction,Collision prediction.Particle i: radius si, po

68、sition (rxi, ryi), velocity (vxi, vyi).Particle j: radius sj, position (rxj, ryj), velocity (vxj, vyj).Will particles i and j collide? If so, when?,Particle-particle collision resolution,Collision resolution. When two

69、particles collide, how does velocity change?,Collision system: event-driven simulation main loop,Initialization.Fill PQ with all potential particle-wall collisions.Fill PQ with all potential particle-particle collisio

70、ns.Main loop.Delete the impending event from PQ (min priority = t).If the event has been invalidated, ignore it.Advance all particles to time t, on a straight-line trajectory.Update the velocities of the colliding