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