欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python數(shù)據(jù)結(jié)構(gòu)與算法之完全樹(shù)與最小堆實(shí)例

 更新時(shí)間:2017年12月13日 11:13:41   作者:hanahimi  
這篇文章主要介紹了Python數(shù)據(jù)結(jié)構(gòu)與算法之完全樹(shù)與最小堆,結(jié)合實(shí)例形式分析了Python完全樹(shù)定義及堆排序功能實(shí)現(xiàn)相關(guān)操作技巧,需要的朋友可以參考下

本文實(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ì)有所幫助。

相關(guān)文章

  • PyCharm中Matplotlib繪圖不能顯示UI效果的問(wè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圖形界面

    這篇文章主要介紹了教你用一行Python代碼實(shí)現(xiàn)GUI圖形界面,通過(guò)使用PySimpleGUI的popup_get_folder()方法,一行代碼就能實(shí)現(xiàn)選擇文件夾的操作,本文結(jié)合示例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下
    2023-01-01
  • python實(shí)現(xiàn)傅里葉級(jí)數(shù)展開(kāi)的實(shí)現(xiàn)

    python實(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-07
  • python實(shí)現(xiàn)靜態(tài)服務(wù)器

    python實(shí)現(xiàn)靜態(tài)服務(wù)器

    這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)靜態(tài)服務(wù)器,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-09-09
  • Python包,__init__.py功能與用法分析

    Python包,__init__.py功能與用法分析

    這篇文章主要介紹了Python包,__init__.py功能與用法,結(jié)合實(shí)例形式分析了Python中包的概念、功能及__init__.py初始化相關(guān)操作技巧,需要的朋友可以參考下
    2020-01-01
  • Python使用requests發(fā)送POST請(qǐng)求實(shí)例代碼

    Python使用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)題

    這篇文章主要介紹了解決jupyter (python3) 讀取文件遇到的問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2021-03-03
  • Pyside2中嵌入Matplotlib的繪圖的實(shí)現(xiàn)

    Pyside2中嵌入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-02
  • Python 計(jì)算機(jī)視覺(jué)編程進(jìn)階之OpenCV 進(jìn)行霍夫變換

    Python 計(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ù)圖的教程

    這篇文章主要介紹了在Linux下使用Python的matplotlib繪制數(shù)據(jù)圖的教程,matplotlib基于Numpy進(jìn)行科學(xué)計(jì)算上的延伸,需要的朋友可以參考下
    2015-06-06

最新評(píng)論