第9章優(yōu)先隊列

第9章優(yōu)先隊列第一頁，共53頁。2本章內容9.1引言9.2線性表9.3堆9.4左高樹9.5應用第二頁，共53頁。堆的實現堆排序左高樹霍夫曼編碼本章重點4/17/20233第三頁，共53頁。49.1引言優(yōu)先隊列優(yōu)先隊列（priorityqueue）是0個或多個元素的集合，

每個元素都有一個優(yōu)先權或值。與FIFO結構的隊列不同，優(yōu)先隊列中元素出隊列的順序由元素的優(yōu)先級決定。從優(yōu)先隊列中刪除元素是根據優(yōu)先權高或低的次序，而不是元素進入隊列的次序.對優(yōu)先隊列執(zhí)行的操作有:1)查找一個元素2)插入一個新元素3)刪除一個元素第四頁，共53頁。5優(yōu)先隊列兩種優(yōu)先隊列:最小優(yōu)先隊列（Minpriorityqueue）最大優(yōu)先隊列（Maxpriorityqueue）在最小優(yōu)先隊列(Minpriorityqueue)中，“查找/刪除”操作用來“搜索/刪除”優(yōu)先權最小的元素；在最大優(yōu)先隊列（Maxpriorityqueue）中，“查找/刪除”操作用來“搜索/刪除”優(yōu)先權最大的元素。優(yōu)先權隊列中的元素可以有相同的優(yōu)先權。第五頁，共53頁。6最大優(yōu)先權隊列的抽象數據類型描述抽象數據類型MaxPriorityQueue{實例有限的元素集合，每個元素都有一個優(yōu)先權操作Create()：創(chuàng)建一個空的優(yōu)先隊列Size()：返回隊列中的元素數目Max()：返回具有最大優(yōu)先權的元素Insert(x)：將x插入隊列DeleteMax(x)：從隊列中刪除具有最大優(yōu)先權的元素，并將該元素返回至x}最小優(yōu)先權隊列的抽象數據類型描述?第六頁，共53頁。7優(yōu)先隊列的描述優(yōu)先隊列的描述線性表堆（Heaps）左高樹（Leftisttrees）第七頁，共53頁。89.2線性表采用無序線性表描述最大優(yōu)先隊列公式化描述（利用公式Location(i)=i-1)插入：表的右端末尾執(zhí)行，時間:(1);刪除:查找優(yōu)先權最大的元素，時間:(n);使用鏈表，插入：在鏈頭執(zhí)行，時間:(1);刪除:(n);采用有序線性表描述最大優(yōu)先隊列公式化描述（利用公式Location(i)=i-1，元素按遞增次序排列)插入:O(n);刪除:O(1);使用鏈表（按遞減次序排列）插入:O(n);刪除:O(1);第八頁，共53頁。99.3堆(Heaps)9.3.1定義

定義[最大樹（最小樹）]

每個節(jié)點的值都大于（小于）或等于其子節(jié)點（如果有的話）值的樹。最大樹或最小樹節(jié)點的子節(jié)點個數可以大于2。第九頁，共53頁。最大（?。?/17/202310第十頁，共53頁。11定義[最大堆（最小堆）]

：最大（最?。┑耐耆鏄洹?46793863986726517第十一頁，共53頁。12判斷哪些是最大（?。┒?？

第十二頁，共53頁。13堆是完全二叉樹，可用一維數組有效地描述堆.986726517987672651……012345678910第十三頁，共53頁。149.3.2最大堆的插入9867726515

新元素是5第十四頁，共53頁。159.3.2最大堆的插入98677265120

新元素是20第十五頁，共53頁。169.3.2最大堆的插入98672651720第十六頁，共53頁。179.3.2最大堆的插入96726517820第十七頁，共53頁。189.3.2最大堆的插入67265178920第十八頁，共53頁。199.3.2最大堆的插入插入的時間復雜性:每一層的工作，耗時：(1)實現插入策略的時間復雜性為：O(height)=O(log2n),（

n

是堆的大小）第十九頁，共53頁。209.3.3最大堆的刪除最大元素在根上。2067265171589第二十頁，共53頁。219.3.3最大堆的刪除最大元素被刪除以后67265171589第二十一頁，共53頁。229.3.3最大堆的刪除具有10個節(jié)點的堆.在堆中重新插入8.67265171589第二十二頁，共53頁。239.3.3最大堆的刪除67265171598需要進行調整（或重構）。左子樹和右子樹是最大堆第二十三頁，共53頁。249.3.3最大堆的刪除67265179158第二十四頁，共53頁。259.3.3最大堆的刪除67265178159第二十五頁，共53頁。269.3.3最大堆的刪除刪除的時間復雜性:刪除的時間復雜性與插入的時間復雜性相同.每一層的工作，耗時：(1)實現刪除策略的時間復雜性為：O(height)=O(log2n),（

n

是堆的大?。┑诙摚?3頁。279.3.4最大堆的初始化1.通過在初始化為空的堆中執(zhí)行n次插入操作來構造。O(nlog2n)更快的堆的初始化策略？2.通過必要時對樹進行調整的方法構造。(n)第二十七頁，共53頁。從第一個具有孩子的節(jié)點開始，這個元素在數組中的位置為i=[n/2]如果以這個元素為根的子樹已是最大堆，則此時不需調整否則必須調整子樹使之成為堆。隨后，繼續(xù)檢查以i-1,i-2等節(jié)點為根的子樹直到檢查到整個二叉樹的根節(jié)點（其位置為1）。思想4/17/202328第二十八頁，共53頁。299.3.4最大堆的初始化

例:輸入數組=[1,2,3,4,5,6,7,8,9,10,11]4678931115210第二十九頁，共53頁。309.3.4最大堆的初始化從數組中最右一個有孩子的節(jié)點開始這個元素的位置i=n/2.4106789311152第三十頁，共53頁。319.3.4最大堆的初始化4678931015112第三十一頁，共53頁。329.3.4最大堆的初始化4678931015112第三十二頁，共53頁。339.3.4最大堆的初始化4678310151129第三十三頁，共53頁。349.3.4最大堆的初始化4678310151129第三十四頁，共53頁。359.3.4最大堆的初始化4678310151129第三十五頁，共53頁。369.3.4最大堆的初始化4678310151129第三十六頁，共53頁。379.3.4最大堆的初始化467831015119為

2找位置第三十七頁，共53頁。389.3.4最大堆的初始化467831015119為2找位置第三十八頁，共53頁。399.3.4最大堆的初始化4678321015119第三十九頁，共53頁。409.3.4最大堆的初始化4678321015119第四十頁，共53頁。419.3.4最大堆的初始化467832101159為

1找位置第四十一頁，共53頁。429.3.4最大堆的初始化467832115109為

1找位置第四十二頁，共53頁。439.3.4最大堆的初始化467832511109為

1找位置第四十三頁，共53頁。449.3.4最大堆的初始化4678325111109第四十四頁，共53頁。45初始化堆的時間復雜性:

堆的高度=h.

在j層節(jié)點的數目<=2j-1.

以j層節(jié)點為根的子樹的高度=h-j+1調整（或重構）以j層節(jié)點為根的子樹：O(h-j+1).

調整（或重構）所有以j層節(jié)點為根的子樹：<=2j-1(h-j+1)=t(j).

總的時間：t(1)+t(2)+…+t(h-1)=O(2h)=O(n).第四十五頁，共53頁。9.3.5類MaxHeaptemplate<classT>classMaxHeap{ public: MaxHeap(intMaxHeapSize=10); ~MaxHeap(){delete[]heap;} intSize()const{returnCurrentSize;} TMax(){if(CurrentSize==0)throwOutOfBounds(); returnheap[1];} MaxHeap<T>&Insert(constT&x); MaxHeap<T>&DeleteMax(T&x); voidInitialize(Ta[],intsize,intArraySize); private: intCurrentSize,MaxSize; T*heap;//元素數組};4/17/202346第四十六頁，共53頁。47堆是完全二叉樹，可用一維數組有效地描述堆.986726517987672651……012345678910currentsizeMaxsizeheap第四十七頁，共53頁。48MaxHeap構造函數template<classT>MaxHeap<T>::MaxHeap(intMaxHeapSize){//構造函數MaxSize=MaxHeapSize;heap=newT[MaxSize+1];CurrentSize=0;}第四十八頁，共53頁。最大堆的插入template<classT>MaxHeap<T>&MaxHeap<T>::Insert(constT&x){//把x插入到最大堆中

if(CurrentSize==MaxSize) throwNoMem(); //為x尋找相應插入位置

//i從新的葉節(jié)點開始，并沿著樹上升

inti=++CurrentSize；

while(i!=1&&x>heap[i/2]){ //不能把x放入heap[i]

heap[i]=heap[i/2];

i/=2; }heap[i]=x; return*this;}4/17/202349第四十九頁，共53頁。最大堆的刪除（1/2）template<classT>MaxHeap<T>&MaxHeap<T>::DeleteMax(T&x){//將最大元素放入x，并從堆中刪除最大元素

//檢查堆是否為空

if(CurrentSize==0) throwOutOfBounds();//隊列空

x=heap[1];//最大元素

//重構堆

Ty=heap[CurrentSize--];//最后一個元素

//從根開始，為y尋找合適的位置

inti=1,//堆的當前節(jié)點

ci=2;//i的孩子

4/17/20234/17/202350第五十頁，共53頁。最大堆的刪除（2/2）while(ci<=CurrentSize){ //heap[ci]應該是i較大的孩子

if(ci<CurrentSize&&heap[ci]<heap[ci+1])

ci++;

//能把y放入heap[i]嗎？

if(y>=heap[ci])break;//能

//