第11章優(yōu)先隊(duì)列9e5c05cf dc9b 4abf 9f58 9ea59bf82a3e

學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)2第11優(yōu)第11優(yōu)先隊(duì)列的原排隊(duì)上車(chē)，老弱病殘者優(yōu)先上排隊(duì)候診，危急病人優(yōu)先就洗相館為顧客洗照片，加錢(qián)加急者優(yōu)先分時(shí)操作系統(tǒng)運(yùn)行程序，小程序優(yōu)在一個(gè)集合中搜索，按元素的某種特征值，大(或小)的優(yōu)先……處理或服務(wù)時(shí)只關(guān)心對(duì)象中誰(shuí)的優(yōu)先級(jí)最通常的隊(duì)列是一種優(yōu)先隊(duì)列最先到者優(yōu)先級(jí)最優(yōu)先隊(duì)3優(yōu)先隊(duì)列優(yōu)先隊(duì)列的定優(yōu)先隊(duì)列也是一個(gè)以集合為基礎(chǔ)的抽象數(shù)據(jù)類(lèi)型優(yōu)先隊(duì)列中的每一個(gè)元素都有一個(gè)優(yōu)先級(jí)值。優(yōu)先隊(duì)列中元素的優(yōu)先級(jí)值記為)是一個(gè)一般的全序集中的元素。優(yōu)先級(jí)值用來(lái)表示該元素出列的優(yōu)先級(jí)。通常約定優(yōu)先級(jí)值小的優(yōu)先級(jí)高。也可以約定優(yōu)先級(jí)值大的優(yōu)先級(jí)高。4優(yōu)先隊(duì)列的定優(yōu)先隊(duì)列的定優(yōu)先隊(duì)列支持的基本運(yùn)算有(1)Min(H)：返回優(yōu)先隊(duì)列H中具有最小優(yōu)先級(jí)的元素H)：將元素x插入優(yōu)先隊(duì)列H(3)DeleteMin(H)：刪除并返回優(yōu)先隊(duì)列H中具有最小優(yōu)級(jí)的元素5用字典實(shí)用字典實(shí)現(xiàn)優(yōu)先隊(duì)優(yōu)先隊(duì)列與字典的相似性與區(qū)別優(yōu)先隊(duì)列中元素的優(yōu)先級(jí)值可以看作是字典中元素的線性在字典中，不同的元素具有不同的線性序值，其插入運(yùn)算僅當(dāng)要插入元素x的線性序值與當(dāng)前字典中所有元素的線性入6用字典實(shí)現(xiàn)優(yōu)先用字典實(shí)現(xiàn)優(yōu)先隊(duì)由于優(yōu)先隊(duì)列與字典的相似性,除了散列表之外，所有現(xiàn)字典的方法都可用于實(shí)現(xiàn)優(yōu)先隊(duì)列用有序鏈表實(shí)現(xiàn)優(yōu)先隊(duì)列;(Insert低效用AVL樹(shù)實(shí)現(xiàn)優(yōu)先隊(duì)列;(邏輯復(fù)雜用無(wú)序鏈表實(shí)現(xiàn)優(yōu)先隊(duì)列Min均低效都有缺點(diǎn)。原因在于沒(méi)有考慮到優(yōu)先隊(duì)列的特性7優(yōu)先級(jí)樹(shù)優(yōu)先級(jí)樹(shù)和優(yōu)先隊(duì)列的特征DeleteMin和Min只關(guān)心優(yōu)先級(jí)最高的元Insert的元素不要求全局的序關(guān)lMiMi，而對(duì)根據(jù)這兩個(gè)特征，人們發(fā)明了優(yōu)先級(jí)樹(shù)811.3優(yōu)先11.3優(yōu)先級(jí)樹(shù)和優(yōu)先級(jí)樹(shù)的概優(yōu)先級(jí)樹(shù)是滿足下面的優(yōu)先級(jí)性質(zhì)的(1)樹(shù)中每一結(jié)點(diǎn)存儲(chǔ)一個(gè)元素)任一結(jié)點(diǎn)中存儲(chǔ)的元素的優(yōu)先級(jí)值不大(小)于其兒子結(jié)點(diǎn)中存儲(chǔ)的元素的優(yōu)先級(jí)值，即父結(jié)點(diǎn)的優(yōu)先級(jí)不低于其兒相應(yīng)的優(yōu)先級(jí)樹(shù)稱(chēng)為極小(大)化優(yōu)先級(jí)樹(shù)911.3優(yōu)先11.3優(yōu)先級(jí)樹(shù)和用優(yōu)先級(jí)樹(shù)實(shí)現(xiàn)優(yōu)先隊(duì)列仍有不足和)后對(duì)結(jié)構(gòu)的維護(hù)，在最壞情況下，。如果讓優(yōu)先級(jí)樹(shù)近似滿，從而h=[logn]達(dá)到最小，那么，結(jié)果將令人滿意：在最壞情況下，Min()將只需O(1),因而引入堆的概念并用堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列11.3優(yōu)先11.3優(yōu)先級(jí)樹(shù)和堆的概念外形像堆就叫做堆。用堆實(shí)現(xiàn)優(yōu)先隊(duì)列Min()、Insert(x)和DeleteMin(x)運(yùn)算的實(shí)用數(shù)組實(shí)用數(shù)組實(shí)現(xiàn)用數(shù)組表示堆從用數(shù)組表示堆的優(yōu)點(diǎn)存儲(chǔ)緊湊，空間利用率數(shù)組實(shí)現(xiàn)優(yōu)先隊(duì)列極小化堆堆排序算堆的定義：個(gè)元素的序列,,……k滿足下列關(guān)系時(shí)，稱(chēng)之為堆。堆排序算堆的定義：個(gè)元素的序列,,……k滿足下列關(guān)系時(shí)，稱(chēng)之為堆?；?例例9元素（完全二叉樹(shù)的根）必為序列n個(gè)元素的最小值或最大堆排序堆排序算法基本思想：將無(wú)序序列建成一個(gè)堆，得關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?；輸出堆頂?shù)淖钚。ù笾岛?，使剩余的個(gè)元素重又建成一個(gè)堆，則可得到個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列，這個(gè)過(guò)程叫堆排序。堆排序需解決的兩個(gè)問(wèn)題如何由一個(gè)無(wú)序序列建成一個(gè)堆如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？第二個(gè)問(wèn)題解決方法——篩方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱(chēng)這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“篩選”。例 輸出輸出輸出輸出：13輸出：例 輸出輸出輸出輸出：13輸出：1327輸出：13輸出：13輸出 49輸出：1349輸出：13輸出：13輸出：13輸出：13輸出 49輸出：1349輸出：13輸出：1327384950輸出49輸出49 輸出：1327384976輸出49輸出49 輸出：1327384976算法描算法描第一個(gè)問(wèn)題解決方方法：從無(wú)序序列的第n/2個(gè)元素（即此無(wú)序序列對(duì)的完全二叉樹(shù)的最后一個(gè)非終端結(jié)點(diǎn)）素止，進(jìn)行反復(fù)篩選例含8個(gè)元素的無(wú)序序列例含8個(gè)元素的無(wú)序序列算法描算法描算法描時(shí)間復(fù)雜度：最壞情況下空間復(fù)雜度11.5可并11.5可并優(yōu)先隊(duì)可并優(yōu)先隊(duì)列也是一個(gè)以集合為基礎(chǔ)的抽象數(shù)據(jù)類(lèi)型。除了必須支持優(yōu)先隊(duì)列的和運(yùn)算外，可并優(yōu)。用堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，可在O(logn)時(shí)間內(nèi)支持同一優(yōu)隊(duì)列中的基本運(yùn)算。但合并個(gè)不同優(yōu)先隊(duì)列的效率不高。下面討論的左偏樹(shù)結(jié)構(gòu)不但能在時(shí)間內(nèi)支持同一優(yōu)先隊(duì)列中的基本運(yùn)算，而且還能有效地支持個(gè)不同優(yōu)e。11.5可11.5可并優(yōu)先隊(duì)11.5.1左偏樹(shù)的定s(x)=min{s(L)，s(R)}+11.5可并11.5可并優(yōu)先隊(duì)11.5.1左偏樹(shù)的定一棵優(yōu)先級(jí)樹(shù)是一棵左偏高樹(shù)，當(dāng)且僅當(dāng)在該樹(shù)的每?jī)?nèi)結(jié)點(diǎn)處，其左兒子結(jié)點(diǎn)的高（值）點(diǎn)的高（值）。對(duì)于二叉樹(shù)中任意一個(gè)結(jié)點(diǎn)x，其重量w(x)遞歸地定義為w(x)=w(L)+w(R)+其中和分別是結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)處，其左兒子結(jié)點(diǎn)的重值）大于或等于其右兒子結(jié)點(diǎn)的重（值）。AALeftists()Values22121101110000s()Values221211011100000000011.5可并優(yōu)先11.5可并優(yōu)先隊(duì)左偏高樹(shù)的性左偏高樹(shù)具有下面性質(zhì)設(shè)x是一棵左偏高樹(shù)的任意一個(gè)內(nèi)結(jié)點(diǎn)，(1)以x為根的子樹(shù)中至少有2^s(x)-1個(gè)結(jié)點(diǎn)。(3)從x出發(fā)的最右路經(jīng)的長(zhǎng)度恰為s(x)問(wèn)題的問(wèn)題的提出已知一個(gè)文本文件，要求把它轉(zhuǎn)換成一個(gè)電子文檔，以便存儲(chǔ)在磁介質(zhì)中或在網(wǎng)絡(luò)上傳輸。從存儲(chǔ)的角度看，我們自然希望該電子文檔越短越好，即存儲(chǔ)占用的空間越少越好；從傳輸?shù)慕嵌瓤?，我們自然也希望該電子文檔越短越好，即傳輸占用的時(shí)間越少越好。因此，我們要求轉(zhuǎn)換成的電子文有許多名家說(shuō)過(guò)，把一個(gè)問(wèn)題表述清楚了，就已經(jīng)解決了問(wèn)題的一半。這說(shuō)明問(wèn)題的表述很重要，表述得越清楚、越表述Huffman編碼問(wèn)表述Huffman編碼問(wèn)題的準(zhǔn)對(duì)涉及的有關(guān)對(duì)象、概念、術(shù)語(yǔ)、和記號(hào)的準(zhǔn)一個(gè)文本文件就是一個(gè)字符串，記為F文本文件中所用到的不同的字符組成的集合，記為CC中的字符c在文件中出現(xiàn)的頻率/次數(shù)，記為f(c)或fc字符編碼的碼長(zhǎng)——0/1串的串長(zhǎng)。記c∈C的碼長(zhǎng)為l(c)文件編碼的碼長(zhǎng)原文本文件編碼后的串的累計(jì)長(zhǎng)。記為L(zhǎng)(F)c∈Cf(c)*l(c)。ASCII碼是一種定長(zhǎng)編碼。不可能壓縮字符的定長(zhǎng)編碼字符的變長(zhǎng)編碼——字符的碼長(zhǎng)隨字符而變表述Huffman編碼問(wèn)題的準(zhǔn)備（續(xù)表述Huffman編碼問(wèn)題的準(zhǔn)備（續(xù)1100}可表示成右圖的二叉樹(shù)。這棵樹(shù)01a101d0c01b1e0fHuffman編碼Huffman編碼問(wèn)題的表述——問(wèn)題數(shù)學(xué)經(jīng)上述準(zhǔn)備，我們看到，字符C的碼長(zhǎng)l)正是c在字符集C的前綴編碼樹(shù)T中的深度，記為T(mén))。這樣，我們的現(xiàn)的頻率/次數(shù)f(c)，要求C的一棵最優(yōu)的前綴編碼樹(shù)T，使得F的編碼長(zhǎng)∑c∈Cf(c)*dT(c)≡B(T)達(dá)到最小。這棵最優(yōu)的Huffman編碼求解問(wèn)求解問(wèn)題的設(shè)想與分(1)問(wèn)題的目標(biāo)是求C的最優(yōu)前綴編碼樹(shù)T，因此，我們應(yīng))這需要證明。求解問(wèn)求解問(wèn)題的設(shè)想與分析（續(xù))和f(z的父結(jié)點(diǎn)，得到一棵新的健全二叉編∪{z這)。若上述設(shè)想與分析正確，那么，問(wèn)題就有了解法：把C中的字符以其頻度為優(yōu)先級(jí)值，且以小者優(yōu)先組織成優(yōu)先隊(duì)列Q。然后反復(fù)地執(zhí)行下面兩個(gè)語(yǔ)句：①刪除Q中優(yōu)先級(jí)最高的兩個(gè)字符，設(shè)為x和②虛擬字符z(分別以x和y為左和右兒子)，并賦予優(yōu)先f(wàn)(z)=f(x)+f(y)，插入直到Q為空，其結(jié)果就是C的最優(yōu)前綴編碼樹(shù)Huffman編碼Huffman編碼問(wèn)題的解n編碼問(wèn)題，在求解問(wèn)題的設(shè)想與分和所猜想的分別是問(wèn)題的解的貪心選擇性質(zhì)和n編碼和解碼的簡(jiǎn)潔實(shí)現(xiàn)。Huffman編碼Huffman編碼問(wèn)題的解決（續(xù))是中具有最小頻度的具有最長(zhǎng)的相證明Huffman編碼問(wèn)題的Huffman編碼問(wèn)題的解決（續(xù)