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