數(shù)據(jù)結(jié)構(gòu)與算法(Python語言描述)課件DS_053_優(yōu)先級(jí)隊(duì)列和堆排序

1、優(yōu)先級(jí)隊(duì)列、堆排序優(yōu)先級(jí)隊(duì)列、堆排序2016 Fall 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)2021-12-161中國海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院中國海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列Priority Queue2021-12-16l與棧和隊(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-12-16優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列l(wèi)代表了數(shù)據(jù)的某種性質(zhì)：代表了數(shù)據(jù)的某種性質(zhì)：n各項(xiàng)工作的計(jì)劃開

2、始時(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-12-16class PrioQue: def _init_(self, elist = ): self.elems = list(elist) self.elems.sort(reverse = True) # 由大到小排序由大到小排序 def is_empty(self): return self.elems = def peek(self): if self.is_emp

3、ty(): raise PrioQueueError(in top) return self.elems-1實(shí)現(xiàn)方式實(shí)現(xiàn)方式1：sorted list2021-12-16 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 -= 1 else: brea

4、k 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-12-16l 入隊(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-12-16堆結(jié)構(gòu)堆結(jié)構(gòu)Heap2021-12-16大頂堆大頂堆 和和 小頂堆小頂堆l堆頂?shù)亩秧?/p>

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

6、若根結(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-12-16堆的表示堆的表示2021-12-16l適合順序存儲(chǔ)適合順序存儲(chǔ)n結(jié)點(diǎn)結(jié)點(diǎn)i 的孩子：的孩子： 2 * i + 1， 2 * i + 2n結(jié)點(diǎn)結(jié)點(diǎn)i 的雙親：的雙親： ( i -1 )/2 l由根到葉子的路徑長由根到葉子的路徑長 lognn含含有有n個(gè)結(jié)點(diǎn)的

7、完全二叉樹的深度：個(gè)結(jié)點(diǎn)的完全二叉樹的深度： log2n 回憶：完全二叉樹的性質(zhì)回憶：完全二叉樹的性質(zhì)2021-12-16堆的表示堆的表示l順序存儲(chǔ)！順序存儲(chǔ)！012345671236248547305391l含含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 # 把雙親擠下來把雙親擠下來對(duì)應(yīng)小數(shù)上浮對(duì)應(yīng)小數(shù)上浮 i, j = j, (j-1)/2 # 繼續(xù)上行繼續(xù)上行 e

8、lemsi = e時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(logn)siftup向上篩選向上篩選2021-12-16如何由堆中刪除元素？如何由堆中刪除元素？2021-12-16012345671338274976654997輸出堆頂后的輸出堆頂后的siftdown過程過程133827657649499738276576494997973827657649492738976576494927384965764997輸出堆頂后的輸出堆頂后的siftdown過程過程左右兩棵子樹已經(jīng)是堆，左右兩棵子樹已經(jīng)是堆，將將最后一個(gè)最后一個(gè)元素充填堆頂，元素充填堆頂，讓其根據(jù)讓其根據(jù)“重量重量”自然下沉：自然下沉：效果是把

9、小的孩子向上擠！效果是把小的孩子向上擠！siftdown從根開始沿小孩子下行從根開始沿小孩子下行2021-12-16j 是是i的小孩子的小孩子 iii 的小孩子的小孩子 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 elemsj+1 elemsj: j += 1 # 選出小選出小孩子孩子 if e 0: self.siftdown(e, 0, len(elems) #0,len) retu

10、rn e02021-12-16l 初始初始一次性一次性建堆：建堆： O(n)l出隊(duì)列：出隊(duì)列：O(logn)l入隊(duì)列：入隊(duì)列：O(logn)堆方式堆方式2021-12-16堆排序堆排序HeapSort2021-12-16lstep1：對(duì)序列建堆；：對(duì)序列建堆；lstep2： 不斷輸出堆頂元素，然后通過不斷輸出堆頂元素，然后通過siftdown再再次調(diào)整成元素?cái)?shù)少次調(diào)整成元素?cái)?shù)少1的堆，直到所有元素輸出。的堆，直到所有元素輸出。堆結(jié)構(gòu)的應(yīng)用堆結(jié)構(gòu)的應(yīng)用堆排序堆排序2021-12-16堆排序堆排序2021-12-16小頂堆排序的結(jié)果是由大到??！小頂堆排序的結(jié)果是由大到??！堆排序堆排序def hea

11、p_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 = e end = len(elems) for i in range(end/2-1, -1, -1): # 初始建堆初始建堆 siftdown(elems, elemsi, i, end) for

12、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 lognl空間：空間：O(1)堆排序的復(fù)雜度分析堆排序的復(fù)雜度分析2021-12-16小結(jié)小結(jié)2021-12-16l堆結(jié)構(gòu)的特點(diǎn)堆結(jié)構(gòu)的特點(diǎn)n邏輯上是邏輯上是“基本有序基本有序”的完全二叉樹，小頂堆堆頂最??！的完全二叉樹，小頂堆堆頂最??！l堆調(diào)整堆調(diào)整nSi