優(yōu)先級(jí)隊(duì)列、堆排序2016Fall《數(shù)據(jù)結(jié)構(gòu)》2022/12/191優(yōu)先級(jí)隊(duì)列

PriorityQueue2022/12/19與棧和隊(duì)列一樣：可以保存數(shù)據(jù)元素，訪問(wèn)、入、出不同之處：每個(gè)數(shù)據(jù)都附有優(yōu)先級(jí)，任何時(shí)候訪問(wèn)、出對(duì)列的總是當(dāng)前隊(duì)列中最優(yōu)先的元素“有序”隊(duì)列！2022/12/19優(yōu)先級(jí)隊(duì)列classPrioQue:def__init__(self,elist=[]):self.elems=list(elist)

self.elems.sort(reverse=True)#由大到小排序 defis_empty(self):returnself.elems==[]defpeek(self):ifself.is_empty():raisePrioQueueError("intop")returnself.elems[-1]實(shí)現(xiàn)方式1：sortedlist2022/12/19

defdequeue(self):ifself.is_empty():raisePrioQueueError("inpop")returnself.elems.pop()

#元素由大到小排，直接pop

defenqueue(self,e):i=len(self.elems)-1whilei>=0:ifself.elems[i]<=e:i-=1else:

breakself.elems.insert(i+1,e)

#循環(huán)結(jié)束時(shí)，遇到了第一個(gè)大于e的元素elems[i]

#入隊(duì)列的時(shí)間復(fù)雜度：O(n)2022/12/19

入隊(duì)列時(shí)保持有序，出隊(duì)列直接pop；入隊(duì)列：O(n)出對(duì)列：O(1)入隊(duì)列時(shí)不處理，出隊(duì)列時(shí)搜索最優(yōu)先：入隊(duì)列：O(1)出隊(duì)列：O(n)線性方式兩種策略2022/12/19堆結(jié)構(gòu)

Heap2022/12/19堆頂?shù)摹皟?yōu)先級(jí)”最高

【數(shù)最小~~小頂堆】上面輕，下面沉；上面氣泡，下面石頭氣泡上浮，石頭下沉“土堆”2022/12/19堆（遞歸定義）空樹；若非空，是一棵完全二叉樹，滿足：若根結(jié)點(diǎn)有左孩子，則根結(jié)點(diǎn)值小于等于其左孩子值；若根結(jié)點(diǎn)有右孩子，則根結(jié)點(diǎn)值小于等于其右孩子值；左右子樹仍然是堆！堆的表示2022/12/19適合順序存儲(chǔ)結(jié)點(diǎn)i的孩子：2*i+1，2*i+2結(jié)點(diǎn)i的雙親：(i-1)/2由根到葉子的路徑長(zhǎng)~logn含有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度：log2n

回憶：完全二叉樹的性質(zhì)2022/12/19堆的表示順序存儲(chǔ)?。?！

012345671236248547305391含n個(gè)元素的線性序列elem[0,…n-1]，滿足：elem[i]<=elem[2*i+1]，如果2*i+1<nelem[i]<=elem[2*i+2]，如果2*i+2<n堆的另一種定義2022/12/19012345671236248547305391存儲(chǔ)上：線性結(jié)構(gòu)邏輯上：完全二叉樹（層次結(jié)構(gòu)）對(duì)堆結(jié)構(gòu)的理解2022/12/19如何向堆中插入元素？？？2022/12/1901234567123624854730539125尾部插入元素后的siftup123624304785539125123624304725539185122524304736539185

defsiftup(self,e,last):#i上行范圍[last,0)elems=self.elemsi,j=last,(last-1)//2#j是i的雙親

whilei>0ande<elems[j]:elems[i]=elems[j]#把雙親擠下來(lái)——對(duì)應(yīng)小數(shù)上浮i,j=j,(j-1)//2#繼續(xù)上行

elems[i]=e

時(shí)間復(fù)雜度：O(logn)siftup——向上篩選2022/12/19如何由堆中刪除元素？？？2022/12/19012345671338274976654997輸出堆頂后的siftdown過(guò)程左右兩棵子樹已經(jīng)是堆，將最后一個(gè)元素充填堆頂，讓其根據(jù)“重量”自然下沉：效果是把小的孩子向上擠！siftdown——從根開始沿小孩子下行2022/12/19j是i的小孩子

iii的小孩子j

defsiftdown(self,e,begin,end):#j的下行范圍<end

elems=self.elems,i,j=begin,begin*2+1whilej<end:ifj+1<endandelems[j+1]<elems[j]:j+=1#選出小孩子

ife<elems[j]:breakelems[i]=elems[j]#孩子擠上去——對(duì)應(yīng)大數(shù)下沉i,j=j,2*j+1#繼續(xù)下行elems[i]=e

時(shí)間復(fù)雜度：O(logn)siftdown——向下篩選2022/12/19如何建堆？？？2022/12/194938651376972749012345674938659776132749明確：

最先一個(gè)沒(méi)有孩子的結(jié)點(diǎn)的編號(hào)為：(n-1-1)/2+1=n/2

從n/2開始的每個(gè)結(jié)點(diǎn)沒(méi)有孩子，各自成一個(gè)堆

如何建堆？？？2022/12/194938651376972749n=8index(76)=4起始：對(duì)于最后一個(gè)有孩子的結(jié)點(diǎn)，它的左右子樹都已經(jīng)是堆；自后向前，逐結(jié)點(diǎn)進(jìn)行siftdown操作，將子堆不斷合成更大些的堆，最終形成一個(gè)大堆。建堆過(guò)程2022/12/19建堆過(guò)程從最后一個(gè)有孩子的結(jié)點(diǎn)開始，逐個(gè)siftdown

defbuildheap(self):end=len(self.elems)foriinrange(end//2-1,-1,-1):self.siftdown(self.elems[i],i,end)

#siftdown操作范圍：[i,end)

建堆2022/12/19建堆的時(shí)間復(fù)雜度2022/12/19建堆時(shí)，從倒數(shù)第二層的加點(diǎn)開始，自后向前，逐步進(jìn)行siftdown；siftdown過(guò)程中，每一步做兩次比較；兩個(gè)孩子選出最小的sift的結(jié)點(diǎn)和小的孩子結(jié)點(diǎn)比較

第i層向下sift的層數(shù)最多為h-i第i層最多2i個(gè)結(jié)點(diǎn)總的比較次數(shù)為：時(shí)間復(fù)雜度：O(n)建堆的時(shí)間復(fù)雜度2022/12/19優(yōu)先級(jí)隊(duì)列的堆實(shí)現(xiàn)2022/12/19classPrioQueue:def__init__(self,elist=[]):self.elems=list(elist)ifelist!=[]:

self.buildheap() defis_empty(self):returnlen(self.elems)==0defpeek(self):ifself.is_empty():raisePrioQueueError("intop")returnself.elems[0]

實(shí)現(xiàn)方式2：堆2022/12/19defenqueue(self,e):self.elems.append(None)#添加占位self.siftup(e,len(self.elems)-1)#last

defdequeue(self):ifself.is_empty():raisePrioQueueError("inpop")elems=self.elems

e0=elems[0]e=elems.pop()#彈出最后一個(gè)，“占位”elem[0]iflen(elems)>0:self.siftdown(e,0,len(elems))#[0,len)returne02022/12/19

初始一次性建堆：O(n)出隊(duì)列：O(logn)入隊(duì)列：O(logn)堆方式2022/12/19堆排序

HeapSort2022/12/19step1：對(duì)序列建堆；step2：不斷輸出堆頂元素，然后通過(guò)siftdown再次調(diào)整成元素?cái)?shù)少1的堆，直到所有元素輸出。堆結(jié)構(gòu)的應(yīng)用——堆排序2022/12/19堆排序2022/12/19小頂堆排序的結(jié)果是由大到小！堆排序defheap_sort(elems):defsiftdown(elems,e,begin,end):#[begin,end)i,j=begin,begin*2+1whilej<end:ifj+1<endandelems[j+1]<elems[j]:j+=1ife<elems[j]:breakelems[i]=elems[j]i,j=j,2*j+1elems[i]=e

end=len(elems)foriinrange(end//2-1,-1,-1):#初始建堆siftdown(elems,elems[i],i,end)

foriinrange((end-1),0,-1):#不斷輸出堆頂，然后調(diào)整e=elems[i]elems[i]=elems[0]#堆頂輸出后，放到當(dāng)前的最后siftdown(elems,e,0,i)#注意：堆的范圍在縮小時(shí)間：O(nlogn)

建堆：O(n)

不斷輸出堆頂、調(diào)整：O(nlogn)