優(yōu)先級隊(duì)列的構(gòu)造

優(yōu)先級隊(duì)列的構(gòu)造優(yōu)先級隊(duì)列的構(gòu)造

優(yōu)先隊(duì)列的類定義優(yōu)先權(quán)應(yīng)用隊(duì)列的構(gòu)造1優(yōu)先級隊(duì)列的構(gòu)造2如果我們給每個元素都分配一個數(shù)字來標(biāo)記其優(yōu)先級，不妨設(shè)較小的數(shù)字具有較高的優(yōu)先級，這樣我們就可以在一個集合中訪問優(yōu)先級最高的元素并對其進(jìn)行查找和刪除操作了。這樣，我們就引入了優(yōu)先級隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)。優(yōu)先級隊(duì)列（priorityqueue）是0個或多個元素的集合，每個元素都有一個優(yōu)先權(quán)，對優(yōu)先級隊(duì)列執(zhí)行的操作有（1）查找（2）插入一個新元素（3）刪除一般情況下，查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素。對于優(yōu)先權(quán)相同的元素，可按先進(jìn)先出次序處理或按任意優(yōu)先權(quán)進(jìn)行。優(yōu)先隊(duì)列的類定義3優(yōu)先權(quán)4優(yōu)先隊(duì)列是0個或多個元素的集合,每個元素都有一個優(yōu)先權(quán)或值,對優(yōu)先隊(duì)列執(zhí)行的操作有1)查找;2)插入一個新元素;3)刪除.在最小優(yōu)先隊(duì)列(minpriorityqueue)中,查找操作用來搜索優(yōu)先權(quán)最小的元素,刪除操作用來刪除該元素;對于最大優(yōu)先隊(duì)列(maxpriorityqueue),查找操作用來搜索優(yōu)先權(quán)最大的元素,刪除操作用來刪除該元素.優(yōu)先權(quán)隊(duì)列中的元素可以有相同的優(yōu)先權(quán),查找與刪除操作可根據(jù)任意優(yōu)先權(quán)進(jìn)行.優(yōu)先權(quán)5最大優(yōu)先權(quán)隊(duì)列的抽象數(shù)據(jù)類型描述如ADT9-1所示,最小優(yōu)先隊(duì)列的抽象數(shù)據(jù)類型描述與之類似,只需將最大改為最小即可。ADT最大優(yōu)先隊(duì)列的抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型MaxPriorityQueue{應(yīng)用6堆排序可以用優(yōu)先級隊(duì)列，堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]]>=A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。應(yīng)用7哈夫曼編碼哈夫曼編碼(HuffmanCoding)是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。大型浮點(diǎn)數(shù)集合的和由于比較小的浮點(diǎn)數(shù)和比較大的浮