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

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