# 完全樹 最小堆
class CompleteTree(list):
  def siftdown(self,i):
    """ 對(duì)一顆完全樹進(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ì)一棵完全樹進(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ì)樹調(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]