數(shù)據(jù)結(jié)構(gòu)課件版章優(yōu)先隊列

2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院1第11章優(yōu)先隊列11.1優(yōu)先隊列的定義11.2用字典實現(xiàn)優(yōu)先隊列11.3優(yōu)先級樹和堆11.4用數(shù)組實現(xiàn)堆11.5可并優(yōu)先隊列11.6優(yōu)先隊列的應(yīng)用吳英杰2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院2第11章優(yōu)先隊列學(xué)習(xí)要點:

理解以集合為基礎(chǔ)的抽象數(shù)據(jù)類型優(yōu)先隊列

理解用字典實現(xiàn)優(yōu)先隊列的方法

理解優(yōu)先級樹和堆的概念

掌握用數(shù)組實現(xiàn)堆的方法理解以集合為基礎(chǔ)的抽象數(shù)據(jù)類型可并優(yōu)先隊列理解左偏樹的定義和概念掌握用左偏樹實現(xiàn)可并優(yōu)先隊列的方法掌握堆排序算法返回章目錄2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院311.1優(yōu)先隊列的定義優(yōu)先隊列的原型排隊上車，老弱病殘者優(yōu)先上車排隊候診，危急病人優(yōu)先就診洗相館為顧客洗照片，加錢加急者優(yōu)先洗分時操作系統(tǒng)運行程序，小程序優(yōu)先貪心算法對解分量的選擇，按元素的某種特征值，大(或小)的優(yōu)先在一個集合中搜索，按元素的某種特征值，大(或小)的優(yōu)先……處理或服務(wù)時只關(guān)心對象中誰的優(yōu)先級最高，通常的隊列是一種優(yōu)先隊列最先到者優(yōu)先級最高2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院411.1優(yōu)先隊列的定義

優(yōu)先隊列也是一個以集合為基礎(chǔ)的抽象數(shù)據(jù)類型。優(yōu)先隊列中的每一個元素都有一個優(yōu)先級值。優(yōu)先隊列中元素x的優(yōu)先級值記為p(x)，它可以是一個實數(shù)，也可以是一個一般的全序集中的元素。優(yōu)先級值用來表示該元素出列的優(yōu)先級。約定優(yōu)先級值小的優(yōu)先級高。亦可約定優(yōu)先級值大的優(yōu)先級高。優(yōu)先隊列支持的基本運算有：(1)Min(H)：返回優(yōu)先隊列H中具有最小優(yōu)先級的元素。(2)Insert(x,H)：將元素x插入優(yōu)先隊列H。(3)DeleteMin(H)：刪除并返回優(yōu)先隊列H中具有最小優(yōu)先級的元素。

返回章目錄2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院511.2用字典實現(xiàn)優(yōu)先隊列(1)優(yōu)先隊列與字典的相似性與區(qū)別：優(yōu)先隊列中元素的優(yōu)先級值可以看作是字典中元素的線性序值。在字典中，不同的元素具有不同的線性序值，其插入運算僅當(dāng)要插入元素x的線性序值與當(dāng)前字典中所有元素的線性序值都不同時才執(zhí)行。對于優(yōu)先隊列來說，不同的元素可以有相同的優(yōu)先級值。因此，優(yōu)先隊列的插入運算即使在當(dāng)前優(yōu)先隊列中存在與要插入元素x有相同的優(yōu)先級值的元素時，也要執(zhí)行元素x的插入。

2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院611.2用字典實現(xiàn)優(yōu)先隊列(2)由于優(yōu)先隊列與字典的相似性,所有實現(xiàn)字典的方法都可用于實現(xiàn)優(yōu)先隊列。用有序鏈表實現(xiàn)優(yōu)先隊列;(Insert低效)用二叉搜索樹實現(xiàn)優(yōu)先隊列;(Insert,DeleteMin,Min

均低效)用AVL樹實現(xiàn)優(yōu)先隊列;(邏輯復(fù)雜)用無序鏈表實現(xiàn)優(yōu)先隊列;(DeleteMin,Min均低效)

……

都有缺點。原因在于沒有考慮到優(yōu)先隊列的特性。返回章目錄2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院711.3用優(yōu)先級樹實現(xiàn)優(yōu)先隊列1.優(yōu)先隊列的特征:DeleteMin和Min只關(guān)心優(yōu)先級最高的元素Insert的元素不要求全局的序關(guān)系因此實現(xiàn)優(yōu)先隊列的結(jié)構(gòu)只要求方便DeleteMin和Min,而對Insert也只要求不給結(jié)構(gòu)的維護帶來太大的麻煩。根據(jù)這兩個特征,人們發(fā)明了優(yōu)先級樹。2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院811.3用優(yōu)先級樹實現(xiàn)優(yōu)先隊列2.優(yōu)先級樹的概念優(yōu)先級樹是滿足下面的優(yōu)先級性質(zhì)的二叉樹：

(1)樹中每一結(jié)點存儲一個元素。

(2)任一結(jié)點中存儲的元素的優(yōu)先級值不大(小)于其兒子結(jié)點中存儲的元素的優(yōu)先級值即父結(jié)點的優(yōu)先級不低于其兒子結(jié)點的優(yōu)先級。 換句話說，越接近根的結(jié)點中的元素的優(yōu)先級越高，越方便被訪問，因為根最方便被訪問。相應(yīng)的優(yōu)先級樹稱為極小(大)化優(yōu)先級樹。返回章目錄2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院911.4用堆實現(xiàn)優(yōu)先隊列用優(yōu)先級樹實現(xiàn)優(yōu)先隊列仍有不足：Insert(x,H)和DeleteMin(H)后對結(jié)構(gòu)的維護，在最壞情況下，仍需O(h)=O(n)。如果讓優(yōu)先級樹近似滿,從而h=[logn],達到最小,那么，在最壞情況下，Min(H)將只需O(1),Insert(x,H)和DeleteMin(H)后對結(jié)構(gòu)的維護只需O(logn)。因而引入堆的概念并用堆來實現(xiàn)優(yōu)先隊列。

(1)堆的概念： 如果一棵優(yōu)先級樹是一棵近似滿二叉樹，那么，這棵具有優(yōu)先級性質(zhì)的近似滿二叉樹(外形像堆)就叫做堆。

(2)用堆實現(xiàn)優(yōu)先隊列：

Min(H)、Insert(x,H)和DeleteMin(H)運算的實現(xiàn)2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院1011.4用數(shù)組表示堆從而實現(xiàn)優(yōu)先隊列(1)用數(shù)組表示堆：從1開始對堆的結(jié)點從根開始自上而下逐層、每層從左到右進行編號，然后讓結(jié)點中的元素按編號在數(shù)組A中與下標(biāo)對號入座。(2)用數(shù)組表示堆的優(yōu)點：存儲緊湊，空間利用率高父子關(guān)系簡單清晰:存放在A[i]的是結(jié)點i的元素,A[2i]和A[2i+1]分別是結(jié)點i的左和右兒子結(jié)點2i和2i+1的元素，A[i/2]是結(jié)點i的父結(jié)點的元素2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院11堆排序算法堆的定義：n個元素的序列(k1,k2,……kn)，當(dāng)且僅當(dāng)滿足下列關(guān)系時，稱之為堆?；?i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1例1（96，83，27，38，11，9）例2（13，38，27，50，76，65，49，97）962791138831327384965765097可將堆序列看成近似滿二叉樹，則堆頂元素（近似滿二叉樹的根）必為序列中n個元素的最小值或最大值2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院12堆排序算法基本思想：將無序序列建成一個堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗洠惠敵龆秧?shù)淖钚。ù螅┲岛?，使剩余的n-1個元素重又建成一個堆，則可得到n個元素的次小值；重復(fù)執(zhí)行，得到一個有序序列，這個過程叫堆排序。堆排序需解決的兩個問題：如何由一個無序序列建成一個堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？第二個問題解決方法——篩選方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并與其中小者進行交換；重復(fù)上述操作，直至葉子結(jié)點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”。2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院13例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：1327382024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院144965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：1327384950652024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院157665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：13273849506576972024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院16算法描述第一個問題解決方法方法：從無序序列的第

n/2個元素（即此無序序列對應(yīng)的完全二叉樹的最后一個非終端結(jié)點）起，至第一個元素止，進行反復(fù)篩選2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院17例含8個元素的無序序列（49，38，65，97，76，13，27，50）496538271376975049653827137650974913382765765097491338276576509713273849657650972024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院18算法描述算法描述時間復(fù)雜度：最壞情況下T(n)=O(nlogn)空間復(fù)雜度：S(n)=O(n)返回章目錄2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院1911.5可并優(yōu)先隊列可并優(yōu)先隊列也是一個以集合為基礎(chǔ)的抽象數(shù)據(jù)類型。除了必須支持優(yōu)先隊列的Insert和DeleteMin運算外，可并優(yōu)先隊列還支持2個不同優(yōu)先隊列的合并運算Concatenate。用堆來實現(xiàn)優(yōu)先隊列，可在O(logn)時間內(nèi)支持同一優(yōu)先隊列中的基本運算。但合并2個不同優(yōu)先隊列的效率不高。下面討論的左偏樹結(jié)構(gòu)不但能在O(logn)時間內(nèi)支持同一優(yōu)先隊列中的基本運算，而且還能有效地支持2個不同優(yōu)先隊列的合并運算Concatenate。2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院2011.5可并優(yōu)先隊列11.5.1左偏樹的定義

左偏樹是一類特殊的優(yōu)先級樹。與優(yōu)先級樹類似，左偏樹也有極小化左偏樹與極大化左偏樹之分。為了確定起見，下面所討論的左偏樹均為極小化左偏樹。常用的左偏樹有左偏高樹和左偏重樹2種不同類型。顧名思義，左偏高樹的左子樹偏高，而左偏重樹的左子樹偏重。下面給出其嚴格定義。若將二叉樹結(jié)點中的空指針看作是指向一個空結(jié)點，則稱這類空結(jié)點為二叉樹的前端結(jié)點。并規(guī)定所有前端結(jié)點的高度（重量）為0。對于二叉樹中任意一個結(jié)點x，遞歸地定義其高度s(x)為：s(x)=min{s(L)，s(R)}+1

其中L和R分別是結(jié)點x的左兒子結(jié)點和右兒子結(jié)點。2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院2111.5可并優(yōu)先隊列11.5.1左偏樹的定義

一棵優(yōu)先級樹是一棵左偏高樹，當(dāng)且僅當(dāng)在該樹的每個內(nèi)結(jié)點處，其左兒子結(jié)點的高（s值）大于或等于其右兒子結(jié)點的高（s值）。對于二叉樹中任意一個結(jié)點x，其重量w(x)遞歸地定義為：w(x)=w(L)+w(R)+1

其中L和R分別是結(jié)點x的左兒子結(jié)點和右兒子結(jié)點。一棵優(yōu)先級樹是一棵左偏重樹，當(dāng)且僅當(dāng)在該樹的每個內(nèi)結(jié)點處，其左兒子結(jié)點的重（w值）大于或等于其右兒子結(jié)點的重（w值）。ALeftistTree0000000000111211212s()ValuesExample2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院2411.5可并優(yōu)先隊列11.5.2左偏高樹的性質(zhì)左偏高樹具有下面性質(zhì)：設(shè)x是一棵左偏高樹的任意一個內(nèi)結(jié)點，則(1)以x為根的子樹中至少有2^s(x)-1個結(jié)點。(2)如果以x為根的子樹中有m個結(jié)點，則s(x)的值不超過log(m+1)。(3)從x出發(fā)的最右路經(jīng)的長度恰為s(x)。返回章目錄2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院25哈夫曼樹(Huffman)——帶權(quán)路徑長度最短的樹定義路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的路徑路徑長度：路徑上的分支數(shù)樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點的路徑長度之和Huffman樹——設(shè)有n個權(quán)值{w1,w2,……wn}，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫Huffman樹11.6優(yōu)先隊列的應(yīng)用2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院26例有4個結(jié)點，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=352024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院27構(gòu)造Huffman樹的方法——Huffman算法構(gòu)造Huffman樹步驟根據(jù)給定的n個權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wj在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹2024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院282024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院29例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d4611182024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院30例：w={5,29,7,8,14,23,3,11}514297823311142978231135887151429233581111358191429238715113581929231487152929148715291135819234211358192342291487152958113581923422914871529581002024/2/3福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院31Huffman算法實現(xiàn)一棵有n個葉子結(jié)點的Huffm