# 完全樹 最小堆
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]