1、優(yōu)先級(jí)隊(duì)列、堆排序優(yōu)先級(jí)隊(duì)列、堆排序 2016 Fall 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 2021-7-281中國海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院中國海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院 優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列 Priority Queue 2021-7-28 l與棧和隊(duì)列一樣：與棧和隊(duì)列一樣： n可以保存數(shù)據(jù)元素，訪問、入、出可以保存數(shù)據(jù)元素，訪問、入、出 l不同之處：每個(gè)數(shù)據(jù)都附有不同之處：每個(gè)數(shù)據(jù)都附有優(yōu)先級(jí)優(yōu)先級(jí)，任何時(shí)候訪，任何時(shí)候訪 問、出對(duì)列的總是當(dāng)前隊(duì)列中最優(yōu)先的元素問、出對(duì)列的總是當(dāng)前隊(duì)列中最優(yōu)先的元素 n“有序有序” 隊(duì)列！隊(duì)列！ 2021-7-28 優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列 l代表了數(shù)據(jù)的某種性質(zhì)：代表了數(shù)據(jù)的某種性質(zhì)

2、： n各項(xiàng)工作的計(jì)劃開始時(shí)間各項(xiàng)工作的計(jì)劃開始時(shí)間 n一個(gè)大項(xiàng)目中各種工作任務(wù)的急迫程度一個(gè)大項(xiàng)目中各種工作任務(wù)的急迫程度 n銀行客戶的誠信評(píng)估，用于決定優(yōu)先貸款等銀行客戶的誠信評(píng)估，用于決定優(yōu)先貸款等 優(yōu)先級(jí)（優(yōu)先級(jí)（Priority） 2021-7-28 class PrioQue: def _init_(self, elist = ): self.elems = list(elist) self.elems.sort(reverse = True) # 由大到小排序由大到小排序 def is_empty(self): return self.elems = def peek(self):

3、 if self.is_empty(): raise PrioQueueError(in top) return self.elems-1 實(shí)現(xiàn)方式實(shí)現(xiàn)方式1：sorted list 2021-7-28 def dequeue(self): if self.is_empty(): raise PrioQueueError(in pop) return self.elems.pop() # 元素由大到小排，直接元素由大到小排，直接pop def enqueue(self, e): i = len(self.elems) - 1 while i = 0: if self.elemsi = e: i

4、 -= 1 else: break self.elems.insert(i+1, e) # 循環(huán)結(jié)束時(shí)，遇到了第一個(gè)大于循環(huán)結(jié)束時(shí)，遇到了第一個(gè)大于e的元素的元素elemsi # 入入隊(duì)列的時(shí)間復(fù)雜度隊(duì)列的時(shí)間復(fù)雜度： O(n) 2021-7-28 l 入隊(duì)列時(shí)保持有序，出隊(duì)列直接入隊(duì)列時(shí)保持有序，出隊(duì)列直接pop； n入隊(duì)列：入隊(duì)列：O(n) n出對(duì)列：出對(duì)列：O(1) l入隊(duì)列時(shí)不處理，出隊(duì)列時(shí)搜索最優(yōu)先：入隊(duì)列時(shí)不處理，出隊(duì)列時(shí)搜索最優(yōu)先： n入隊(duì)列：入隊(duì)列：O(1) n出隊(duì)列：出隊(duì)列：O(n) 線性方式兩種策略線性方式兩種策略 2021-7-28 堆結(jié)構(gòu)堆結(jié)構(gòu) Heap 2021-7-

5、28 大頂堆大頂堆 和和 小頂堆小頂堆 l堆頂?shù)亩秧數(shù)摹皟?yōu)先級(jí)優(yōu)先級(jí)”最高最高 【數(shù)最小數(shù)最小 小頂堆小頂堆】 n上面輕，下面沉；上面輕，下面沉； 上面氣泡，下面石頭上面氣泡，下面石頭 n氣泡上浮，石頭下沉氣泡上浮，石頭下沉 “土堆土堆” 2021-7-28 堆堆 l是是一棵一棵“基本有基本有序序”的完全二叉樹的完全二叉樹 ！ n任何結(jié)點(diǎn)的值都小于等于其左右孩子的值！任何結(jié)點(diǎn)的值都小于等于其左右孩子的值！ 堆（遞歸定義）堆（遞歸定義） n空樹；空樹； n若非空，是一棵完全二叉樹，滿足：若非空，是一棵完全二叉樹，滿足： 若根結(jié)點(diǎn)有左孩子，則根結(jié)點(diǎn)值小于等于其左孩子值；若根結(jié)點(diǎn)有左孩子，則根結(jié)點(diǎn)值

6、小于等于其左孩子值； 若根結(jié)點(diǎn)有右孩子，則根結(jié)點(diǎn)值小于等于其右孩子值；若根結(jié)點(diǎn)有右孩子，則根結(jié)點(diǎn)值小于等于其右孩子值； 左右子樹仍然是堆！左右子樹仍然是堆！ l特點(diǎn)：特點(diǎn)： n最優(yōu)先的元素位于堆頂；最優(yōu)先的元素位于堆頂； n 左右子樹仍然是堆；左右子樹仍然是堆； n 由根到葉子的路徑上，結(jié)點(diǎn)是有序的；由根到葉子的路徑上，結(jié)點(diǎn)是有序的； l應(yīng)用：應(yīng)用： n表示優(yōu)先級(jí)隊(duì)列！表示優(yōu)先級(jí)隊(duì)列！ n堆排序堆排序 堆堆 2021-7-28 堆的表示堆的表示 2021-7-28 l適合順序存儲(chǔ)適合順序存儲(chǔ) n結(jié)點(diǎn)結(jié)點(diǎn)i 的孩子：的孩子： 2 * i + 1， 2 * i + 2 n結(jié)點(diǎn)結(jié)點(diǎn)i 的雙親：的雙親

7、： ( i -1 )/2 l由根到葉子的路徑長由根到葉子的路徑長 logn n含含有有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度：個(gè)結(jié)點(diǎn)的完全二叉樹的深度： log2n 回憶：完全二叉樹的性質(zhì)回憶：完全二叉樹的性質(zhì) 2021-7-28 堆的表示堆的表示 l順序存儲(chǔ)！順序存儲(chǔ)！ 01234567 1236248547305391 l含含n個(gè)元素的線性序列個(gè)元素的線性序列elem0,n-1，滿足：，滿足： nelemi = elem2 * i + 1， 如果如果2*i+1 n nelemi = elem2 * i + 2， 如果如果2*i+2 0 and e elemsj: elemsi = elemsj # 把

8、雙親擠下來把雙親擠下來對(duì)應(yīng)小數(shù)上浮對(duì)應(yīng)小數(shù)上浮 i, j = j, (j-1)/2 # 繼續(xù)上行繼續(xù)上行 elemsi = e 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(logn) siftup向上篩選向上篩選 2021-7-28 如何由堆中刪除元素？如何由堆中刪除元素？ 2021-7-28 01234567 1338274976654997 輸出堆頂后的輸出堆頂后的siftdown過程過程 13 3827 65764949 97 3827 65764949 97 97 3827 65764949 27 3897 65764949 27 3849 65764997 輸出堆頂后的輸出堆頂后的siftdown過

9、程過程 左右兩棵子樹已經(jīng)是堆，左右兩棵子樹已經(jīng)是堆， 將將最后一個(gè)最后一個(gè)元素充填堆頂，元素充填堆頂， 讓其根據(jù)讓其根據(jù)“重量重量”自然下沉：自然下沉： 效果是把小的孩子向上擠！效果是把小的孩子向上擠！ siftdown從根開始沿小孩子下行從根開始沿小孩子下行 2021-7-28 j 是是i的小孩子的小孩子 i i i 的小孩子的小孩子 j def siftdown(self, e, begin, end): # j的下行范圍的下行范圍 end elems = self.elems, i, j = begin, begin*2+1 while j end: if j+1 end and ele

10、msj+1 elemsj: j += 1 # 選出小選出小孩子孩子 if e 0: self.siftdown(e, 0, len(elems) #0,len) return e0 2021-7-28 l 初始初始一次性一次性建堆：建堆： O(n) l出隊(duì)列：出隊(duì)列：O(logn) l入隊(duì)列：入隊(duì)列：O(logn) 堆方式堆方式 2021-7-28 堆排序堆排序 HeapSort 2021-7-28 lstep1：對(duì)序列建堆；：對(duì)序列建堆； lstep2： 不斷輸出堆頂元素，然后通過不斷輸出堆頂元素，然后通過siftdown再再 次調(diào)整成元素?cái)?shù)少次調(diào)整成元素?cái)?shù)少1的堆，直到所有元素輸出。的堆，

11、直到所有元素輸出。 堆結(jié)構(gòu)的應(yīng)用堆結(jié)構(gòu)的應(yīng)用堆排序堆排序 2021-7-28 堆排序堆排序 2021-7-28 小頂堆排序的結(jié)果是由大到小！小頂堆排序的結(jié)果是由大到小！ 堆排序堆排序 def heap_sort(elems): def siftdown(elems, e, begin, end): # begin, end) i, j = begin, begin*2+1 while j end: if j+1 end and elemsj+1 elemsj: j += 1 if e elemsj: break elemsi = elemsj i, j = j, 2*j+1 elemsi =

12、e end = len(elems) for i in range(end/2-1, -1, -1): # 初始建堆初始建堆 siftdown(elems, elemsi, i, end) for i in range(end-1), 0, -1): # 不斷輸出堆頂，然后調(diào)整不斷輸出堆頂，然后調(diào)整 e = elemsi elemsi = elems0 # 堆頂輸出后，放到當(dāng)前的最后堆頂輸出后，放到當(dāng)前的最后 siftdown(elems, e, 0, i) # 注意：堆的范圍在縮小注意：堆的范圍在縮小 l時(shí)間：時(shí)間：O(n logn) n 建堆：建堆：O(n) n 不斷輸出堆頂、調(diào)整：不斷輸出堆頂、調(diào)整： O(n logn) 共共n個(gè)元素個(gè)元素 每個(gè)元素輸出后的每個(gè)元素輸出后的siftdown，不超過樹的深度，不超過樹的深度 log(n-1) + + log(2) n logn l空間：空間：O(1) 堆排序的復(fù)雜度分析堆排序的復(fù)雜度分析 2021-7-28 小結(jié)小結(jié) 2021-7-28 l堆結(jié)構(gòu)的特點(diǎn)堆結(jié)構(gòu)的特點(diǎn) n邏輯上是邏輯上是“基本有序基本有序”的完全二叉樹，小頂堆堆頂最小！的完全二叉樹，小頂堆堆頂最小！ l堆調(diào)整堆調(diào)整 nSiftu