《數(shù)據(jù)結(jié)構(gòu)：思想與方法》第6章優(yōu)先級隊列

1第6章優(yōu)先級隊列基本的優(yōu)先級隊列二叉堆D堆歸并優(yōu)先級隊列STL中的優(yōu)先級隊列排隊系統(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é)點的值大于兒子結(jié)點的值（最大化堆），或者根結(jié)點的值小于兒子結(jié)點的值（最小化堆）4836712515423732102960最大化堆最小化堆4二叉堆的特性結(jié)構(gòu)性：符合完全二叉樹的結(jié)構(gòu)有序性：滿足父節(jié)點小于子節(jié)點（最小化堆）或父節(jié)點大于子節(jié)點（最大化堆）以下的討論都以最小化堆為例5二叉堆的存儲可以采用順序存儲二叉堆的有序性可以很容易地通過下標(biāo)來反映5423732102960234571023296001234567896基于二叉堆的優(yōu)先級隊列

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

。7優(yōu)先級隊列類數(shù)據(jù)成員：用一個動態(tài)數(shù)組成員函數(shù)：實現(xiàn)隊列類的所有操作8優(yōu)先級隊列類的定義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操作是在堆中插入一個新元素堆的插入通常是在具有最大序號的元素之后插入新的元素或結(jié)點。如果新元素放入后，沒有違反堆的有序性，那么操作結(jié)束。否則，讓該節(jié)點向父節(jié)點移動，直到滿足有序性或到達(dá)根節(jié)點。新節(jié)點的向上移動稱為向上過濾(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ù)的平均情況，過濾會提前結(jié)束。有資料表明，平均是2.6次比較，因此元素平均上移1.6層。15DeQueue操作當(dāng)最小元素被刪除時，在根上出現(xiàn)了一個空結(jié)點。堆的大小比以前小1，堆的結(jié)構(gòu)性告訴我們，最后一個結(jié)點應(yīng)該刪掉。如果最后一項應(yīng)該放在此空結(jié)點中，就把它放進去。然而，這是不可能的。我們必須玩與插入操作相同的游戲：把某些項放入空結(jié)點，然后移動空結(jié)點。僅有的區(qū)別在于：對DeQueue操作，空結(jié)點是往下移動。過程：找到空結(jié)點的一個較小的子結(jié)點，如果該兒子的值小于我們要放入的項，則把該兒子放入空結(jié)點，把空結(jié)點往下推一層，重復(fù)這個動作，直到該項能被放入正確的位置，這個過程稱為向下過濾（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操作的性能因為樹有對數(shù)的深度，在最壞情況下，deQueue是一個對數(shù)時間的操作。根據(jù)堆的有序性，堆中最后一個結(jié)點的值一般都是比較大的。因此，向下過濾很少有提前一或二層結(jié)束的，所以deQueue操作平均也是對數(shù)時間。20建堆可以看成N次連續(xù)插入，其時間應(yīng)該是在O(NlogN)時間內(nèi)完成。事實上，在構(gòu)造過程中，我們并不關(guān)心每個元素加入后堆的狀態(tài)，我們關(guān)心的是N個元素全部加入后的最后狀態(tài)，最后的狀態(tài)是要保證堆的有序性。至于中間過程中的有序性是否成立并不重要。有了這個前提后，我們能將構(gòu)造堆的時間復(fù)雜度降到O（N）21建堆過程利用堆的遞歸定義如果函數(shù)buildHeap可以將一棵完全二叉樹調(diào)整為一個堆，那么，只要對左子堆和右子堆遞歸調(diào)用buildHeap。至此，我們能保證除了根結(jié)點外，其余的地方都建立起了堆的有序性。然后對根結(jié)點調(diào)用percolateDown，以創(chuàng)建堆的有序性。事實上并不一定需要遞歸。如果我們以逆向?qū)哟蔚拇涡驅(qū)Y(jié)點調(diào)用percolateDown，那么在percolateDown（i）被處理時，所有結(jié)點i的子孫都已經(jīng)調(diào)用過percolateDown。注意，不需要對葉結(jié)點執(zhí)行percolateDown。因此，我們是從編號最大的非葉結(jié)點開始。22例如，給出的數(shù)據(jù)初值為40，20，60，15，30，25，10，35，45，50，55，構(gòu)造一個最小化堆4035156010302025455055首先，將他看成是一棵完全二叉樹，然后把他調(diào)整成一個堆23403515601030202545505530和15沒有違反堆的有序性，接著調(diào)整604035151060302025455055調(diào)整204035201060301525455055調(diào)整40103520256030154045505524建堆總結(jié)自下往上調(diào)整每一個子堆在調(diào)整每個堆時，假設(shè)除根以外，所有節(jié)點滿足堆的定義根結(jié)點的調(diào)整是一個自上往下的過程：根和他的兒子比較，是否按足堆的定義。如不滿足，找一個大的兒子與他交換。但此時該兒子的子堆的有序性可能遭到破壞。再調(diào)整他的兒子、孫子…直到調(diào)整到葉結(jié)點為止。25建堆

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

26帶有初始數(shù)據(jù)的構(gòu)造函數(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建堆的時間代價分析

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

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

switch(事件類型）

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

case離開：if（等待隊列非空）

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

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

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

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

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

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

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

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

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

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

intcurrentTime;//記錄模擬過程中的時間

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

linkQueue<eventT>waitQueue;//顧客等待隊列

priorityQueue<eventT>eventQueue;//事件隊列

eventTcurrentEvent;

75//生成初始的事件隊列

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