Python數(shù)據(jù)結(jié)構(gòu)與算法之完全樹(shù)與最小堆實(shí)例
本文實(shí)例講述了Python數(shù)據(jù)結(jié)構(gòu)與算法之完全樹(shù)與最小堆。分享給大家供大家參考,具體如下:
# 完全樹(shù) 最小堆 class CompleteTree(list): def siftdown(self,i): """ 對(duì)一顆完全樹(shù)進(jìn)行向下調(diào)整,傳入需要向下調(diào)整的節(jié)點(diǎn)編號(hào)i 當(dāng)刪除了最小的元素后,當(dāng)新增加一個(gè)數(shù)被放置到堆頂時(shí), 如果此時(shí)不符合最小堆的特性,則需要將這個(gè)數(shù)向下調(diào)整,直到找到合適的位置為止""" n = len(self) # 當(dāng) i 節(jié)點(diǎn)有兒子(至少是左兒子時(shí)),并且有需要調(diào)整時(shí),循環(huán)執(zhí)行 t = 0 while i*2+1<n: # step 1:從當(dāng)前結(jié)點(diǎn),其左兒子,其右兒子中找到最小的一個(gè),將其編號(hào)傳給t if self[i] > self[i*2+1]: t = i*2+1 else: t = i # 如果有右兒子,則再對(duì)右兒子進(jìn)行討論 if i*2+2<n: if self[t] > self[i*2+2]: t = i*2+2 # step 2:把最小的結(jié)點(diǎn)中的元素和結(jié)點(diǎn)i的元素交換 if t != i: self[t],self[i] = self[i],self[t] i = t # 更新i為剛才與它交換的兒子結(jié)點(diǎn)的編號(hào),以便接下來(lái)繼續(xù)向下調(diào)整 else: break # 說(shuō)明當(dāng)前父結(jié)點(diǎn)已經(jīng)比兩個(gè)子結(jié)點(diǎn)要小,結(jié)束調(diào)整 def siftup(self,i): """ 對(duì)一棵完全樹(shù)進(jìn)行向上調(diào)整,傳入一個(gè)需要向上調(diào)整的結(jié)點(diǎn)編號(hào)i 當(dāng)要添加一個(gè)新元素后,對(duì)堆底(最后一個(gè))元素進(jìn)行調(diào)整 """ if i==0: return n = len(self) if i < 0: i += n # 注意,由于堆的特性,不需要考慮左兒子結(jié)點(diǎn)的情況 # 由于父結(jié)點(diǎn)絕對(duì)比子結(jié)點(diǎn)小所以只需要比較一次 while i!=0: if self[i]<self[(i-1)/2]: self[i],self[(i-1)/2] = self[(i-1)/2],self[i] else: break i = (i-1)/2 # 更新i為其父結(jié)點(diǎn)編號(hào),從而便于下一次繼續(xù)向上調(diào)整 def shufflePile(self): """ 在當(dāng)前狀態(tài)下,對(duì)樹(shù)調(diào)整使其成為一個(gè)堆 """ # 從"堆底"往"堆頂"進(jìn)行向下調(diào)整,使得最小的元素不斷上升 # 這樣可以使得i結(jié)點(diǎn)以下的堆是局部最小堆 for i in range((len(self)-2)/2,-1,-1): # n/2,...,0 self.siftdown(i) def deleteMin(self): """ 刪除最小元素 """ t = self[0] # 用一個(gè)臨時(shí)變量記錄堆頂點(diǎn)的 self[0] = self[-1] # 將堆的最后一個(gè)點(diǎn)賦值到堆頂 self.pop() # 刪除最后一個(gè)元素 self.siftdown(0) # 向下調(diào)整 return t def heapsort(self): """ 對(duì)堆中元素進(jìn)行堆排序操作 """ n = len(self) s = [] while n>0: s.append(self.deleteMin()) n -= 1 # 由于堆中的元素已全部彈出,將排序好的元素拼接到原來(lái)的堆中 self.extend(s) if __name__=="__main__": a = [99,5,36,7,22,17,92,12,2,19,25,28,1,46] ct = CompleteTree(a) print ct >>> [99, 5, 36, 7, 22, 17, 92, 12, 2, 19, 25, 28, 1, 46] ct.shufflePile() print ct >>> [1, 2, 17, 5, 19, 28, 46, 12, 7, 22, 25, 99, 36, 92] s = ct.heapsort() print ct >>> [1, 2, 5, 7, 12, 17, 19, 22, 25, 28, 36, 46, 92, 99]
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門(mén)與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
- Python數(shù)據(jù)結(jié)構(gòu)與算法之字典樹(shù)實(shí)現(xiàn)方法示例
- Python數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)結(jié)構(gòu)定義與遍歷方法詳解
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的統(tǒng)計(jì)與轉(zhuǎn)換實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的遍歷實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的建立實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)樹(shù)和二叉樹(shù)簡(jiǎn)介
- Python數(shù)據(jù)結(jié)構(gòu)樹(shù)與算法分析
相關(guān)文章
PyCharm中Matplotlib繪圖不能顯示UI效果的問(wèn)題解決
這篇文章主要介紹了PyCharm中Matplotlib繪圖不能顯示UI效果的問(wèn)題解決,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03教你用一行Python代碼實(shí)現(xiàn)GUI圖形界面
這篇文章主要介紹了教你用一行Python代碼實(shí)現(xiàn)GUI圖形界面,通過(guò)使用PySimpleGUI的popup_get_folder()方法,一行代碼就能實(shí)現(xiàn)選擇文件夾的操作,本文結(jié)合示例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01python實(shí)現(xiàn)傅里葉級(jí)數(shù)展開(kāi)的實(shí)現(xiàn)
這篇文章主要介紹了python實(shí)現(xiàn)傅里葉級(jí)數(shù)展開(kāi)的實(shí)現(xiàn),小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-07-07python實(shí)現(xiàn)靜態(tài)服務(wù)器
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)靜態(tài)服務(wù)器,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-09-09Python使用requests發(fā)送POST請(qǐng)求實(shí)例代碼
這篇文章主要介紹了Python使用requests發(fā)送POST請(qǐng)求實(shí)例代碼,小編覺(jué)得還是挺不錯(cuò)的,具有一定借鑒價(jià)值,需要的朋友可以參考下2018-01-01解決jupyter (python3) 讀取文件遇到的問(wèn)題
這篇文章主要介紹了解決jupyter (python3) 讀取文件遇到的問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-03-03Pyside2中嵌入Matplotlib的繪圖的實(shí)現(xiàn)
這篇文章主要介紹了Pyside2中嵌入Matplotlib的繪圖的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02Python 計(jì)算機(jī)視覺(jué)編程進(jìn)階之OpenCV 進(jìn)行霍夫變換
霍夫變換(Hough)是一個(gè)非常重要的檢測(cè)間斷點(diǎn)邊界形狀的方法。它通過(guò)將圖像坐標(biāo)空間變換到參數(shù)空間,來(lái)實(shí)現(xiàn)直線與曲線的擬合,通過(guò)本篇文章我們來(lái)詳細(xì)了解它2021-11-11在Linux下使用Python的matplotlib繪制數(shù)據(jù)圖的教程
這篇文章主要介紹了在Linux下使用Python的matplotlib繪制數(shù)據(jù)圖的教程,matplotlib基于Numpy進(jìn)行科學(xué)計(jì)算上的延伸,需要的朋友可以參考下2015-06-06