本文實例講述了Python數據結構與算法之完全樹與最小堆。分享給大家供大家參考，具體如下：

# 完全樹 最小堆class CompleteTree(list):  def siftdown(self,i):    """ 對一顆完全樹進行向下調整，傳入需要向下調整的節點編號i    當刪除了最小的元素后，當新增加一個數被放置到堆頂時，    如果此時不符合最小堆的特性，則需要將這個數向下調整，直到找到合適的位置為止"""    n = len(self)    # 當 i 節點有兒子（至少是左兒子時），并且有需要調整時，循環執行    t = 0    while i*2+1<n:      # step 1：從當前結點，其左兒子，其右兒子中找到最小的一個，將其編號傳給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：把最小的結點中的元素和結點i的元素交換      if t != i:        self[t],self[i] = self[i],self[t]        i = t  # 更新i為剛才與它交換的兒子結點的編號，以便接下來繼續向下調整      else:        break  # 說明當前父結點已經比兩個子結點要小，結束調整  def siftup(self,i):    """ 對一棵完全樹進行向上調整，傳入一個需要向上調整的結點編號i      當要添加一個新元素后，對堆底（最后一個）元素進行調整 """    if i==0: return    n = len(self)    if i < 0: i += 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為其父結點編號，從而便于下一次繼續向上調整  def shufflePile(self):    """ 在當前狀態下，對樹調整使其成為一個堆 """    # 從"堆底"往"堆頂"進行向下調整，使得最小的元素不斷上升    # 這樣可以使得i結點以下的堆是局部最小堆    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)  # 向下調整    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]