第六章 優(yōu)先級(jí)隊(duì)列

1、數(shù)據(jù)結(jié)構(gòu)Data Structure,第六章 優(yōu)先級(jí)隊(duì)列,第六章 優(yōu)先級(jí)隊(duì)列,基本的優(yōu)先級(jí)隊(duì)列 二叉堆 D堆 歸并優(yōu)先級(jí)隊(duì)列 STL中的優(yōu)先級(jí)隊(duì)列 排隊(duì)系統(tǒng)的模擬,基本的優(yōu)先級(jí)隊(duì)列,結(jié)點(diǎn)之間的關(guān)系是由結(jié)點(diǎn)的優(yōu)先級(jí)決定的，而不是由入隊(duì)的先后次序決定。優(yōu)先級(jí)高的先出隊(duì)，優(yōu)先級(jí)低的后出隊(duì)。這樣的隊(duì)列稱為優(yōu)先級(jí)隊(duì)列。,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)先級(jí)隊(duì)列的簡單實(shí)現(xiàn),利用現(xiàn)有的隊(duì)列結(jié)構(gòu)。有兩種方法可以處理優(yōu)先級(jí) 入隊(duì)時(shí)，按照優(yōu)先級(jí)在隊(duì)列中尋找合適的位置，

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

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é)點(diǎn)小于子節(jié)點(diǎn)

10、（最小化堆）或父節(jié)點(diǎn)大于子節(jié)點(diǎn)（最大化堆） 以下的討論都以最小化堆為例,二叉堆的存儲(chǔ),可以采用順序存儲(chǔ)二叉堆的有序性可以很容易地通過下標(biāo)來反映,基于二叉堆的優(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è)

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

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

13、Queue( const Type data[], int size ); //從一組給定的數(shù)據(jù)創(chuàng)建一個(gè)優(yōu)先級(jí)隊(duì)列 ~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操作是在堆中插入一個(gè)新元素 堆的插入是在具有最大序號(hào)的元素之后插入新的元素或結(jié)點(diǎn)，否則將違反堆的結(jié)構(gòu)性。 如果新元素放入后，沒有違反堆的有序性，那么操作結(jié)束。否則，讓該節(jié)點(diǎn)向父節(jié)點(diǎn)移動(dòng)，直到滿足有序性或到達(dá)根節(jié)點(diǎn)。 新節(jié)點(diǎn)的向上移動(dòng)稱為向上過濾(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é)點(diǎn)的父結(jié)點(diǎn)或已過濾到根時(shí)終止循環(huán)

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

18、，就把它放進(jìn)去。然而，這通常是不可能的。 我們必須玩與插入操作相同的游戲：把某些項(xiàng)放 入空結(jié)點(diǎn)，然后移動(dòng)空結(jié)點(diǎn)。僅有的區(qū)別在于： 對(duì)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)能被放入,? 刪除最小元素,,,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-- ]; //將最后一個(gè)元素挪到根節(jié)點(diǎn) 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é)點(diǎn)小于左（右）孩子，

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

24、入，其時(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）,建堆過程的遞歸實(shí)現(xiàn),利用堆的遞歸定義 如果函數(shù)buildHeap可以將一棵完全二叉樹 調(diào)整為一個(gè)堆 ，那么，只要對(duì)左子堆和右 子堆遞歸調(diào)用buildHea

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

26、 void priorityQueue::buildHeap( ) { for ( int i = currentSize/2; i > 0; i-- ) percolateDown( i ); }currentSize/2: 編號(hào)最大的非葉結(jié)點(diǎn),帶有初始數(shù)據(jù)的構(gòu)造函數(shù)的實(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)造一個(gè)最小化堆,25,40,60,10,35,,60,10,30,,,,,25,,,,45,,50,,55,,15,20,20,15,由給出的數(shù)據(jù)構(gòu)造一棵完全二叉樹,對(duì)結(jié)點(diǎn)30執(zhí)行向下過濾,對(duì)結(jié)點(diǎn)15執(zhí)行向下過濾,對(duì)結(jié)點(diǎn)60執(zhí)行向下過濾,對(duì)結(jié)點(diǎn)20執(zhí)行向下過濾,對(duì)結(jié)點(diǎn)40執(zhí)行向下過濾,定理：對(duì)于一棵高度為h，包含了N = 2h+1 - 1個(gè)結(jié)點(diǎn)的滿二叉樹，結(jié)點(diǎn)的高度和為N – h – 1 證明：高度

29、為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)的高度和為：,建堆的時(shí)間代價(jià)分析,建堆的時(shí)間是O(N)。 高度為h的節(jié)點(diǎn)（葉節(jié)點(diǎn)為0），在 percolateDown中交換的最大次數(shù)是h。 建堆的時(shí)間是所有節(jié)點(diǎn)的調(diào)整時(shí)所需交換 次數(shù)之和，即所有節(jié)點(diǎn)的高度之和 N – h – 1 。,第六章 優(yōu)先級(jí)隊(duì)列,基本的優(yōu)先級(jí)隊(duì)列 二叉堆 D堆 歸并優(yōu)先級(jí)隊(duì)列 STL中的

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

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

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

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

34、。 最壞的時(shí)間復(fù)雜性O(shè)(N)，但對(duì)M個(gè)連續(xù)的操作，最壞的運(yùn)行時(shí)間是O(MlogN)。因此，每個(gè)操作由均攤的O(logN)的時(shí)間復(fù)雜度。 它的操作比左堆簡單。,斜堆的歸并,類似于左堆，只是在左堆中，歸并后左 右子堆的交換是有條件的；而在斜堆中，是無條件的，必須交換。僅有一種例外情況：右路徑上所有節(jié)點(diǎn)中的最大者不需要交換它的孩子。,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)點(diǎn),不需要保存npl 不需要維護(hù)npl 不需要測試npl以決定是否要交換左右子堆,貝努里隊(duì)列,貝努里隊(duì)列支持插入、刪除和歸并操作。 最壞情況下的時(shí)間復(fù)雜性是O(logN)，但平均的插入時(shí)間是一個(gè)常量。 貝努里隊(duì)列表示為一個(gè)貝努里樹的集合。,貝努里樹,貝努里樹是一棵普通的樹，不是二叉樹。 高度為0的貝努里樹是單個(gè)節(jié)點(diǎn)，高度為k的貝努里樹Bk是將一棵Bk-1加到另一棵Bk-1

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

37、出隊(duì),歸并操作,由低到高依次歸并兩個(gè)優(yōu)先級(jí)隊(duì)列中高度 相同的樹。如果由于前一次歸并而出現(xiàn)三 棵高度相同的樹時(shí)，留下一棵，歸并其余 兩棵。 高度相同的樹的歸并：將根節(jié)點(diǎn)大的作為 根節(jié)點(diǎn)小的樹的子樹。 歸并的時(shí)間效益：N個(gè)元素的隊(duì)列有l(wèi)ogN 棵樹，因此最壞情況為O(logN)。,歸并以下兩個(gè)隊(duì)列：,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，留下一棵，歸并其余兩棵,最后的隊(duì)列：,插入,插入是歸并的特例 為被插入節(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é)束。,刪除,找出具有

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

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

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

42、&x) Const Object &top() const Void pop() Bool empty() Void clear(),使用實(shí)例,#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)先級(jí)隊(duì)列,基本的優(yōu)先級(jí)隊(duì)列 二叉堆 D堆 歸并優(yōu)先級(jí)隊(duì)列 STL中的優(yōu)先級(jí)隊(duì)列 排隊(duì)系統(tǒng)的模擬,單服務(wù)臺(tái)的排隊(duì)系統(tǒng),在單服務(wù)臺(tái)系統(tǒng)中

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

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

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

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

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

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

50、錄模擬過程中的時(shí)間 int totalWaitTime = 0; //模擬過程中所有顧客的等待時(shí)間的總和 linkQueue waitQueue; //顧客等待隊(duì)列 priorityQueue eventQueue; //事件隊(duì)列 eventT currentEvent; //當(dāng)前事件,,//產(chǎn)生customNum個(gè)顧客的到達(dá)事件，按到達(dá)時(shí)間大小入隊(duì)，生成初始的事件隊(duì)列 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()) //事件隊(duì)列非空 {currentEvent = eventQueue.deQueue(); //出隊(duì) currentTime = currentEvent.time; //設(shè)置當(dāng)前時(shí)間為該事件發(fā)生的時(shí)間 switch(curr

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

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

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

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

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

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

59、多服務(wù)臺(tái)的排隊(duì)系統(tǒng)的模擬。,作業(yè),程序設(shè)計(jì)題：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