heaptree.py

class heaptree():
    L=[None]
    N=0
    def __init__(self):
        self.L=[None]
        self.N=0
    def debug(self):
        return self.L
    def heappush(self,v):
        self.L.append(v)
        self.N+=1
        i=self.N
        while(i>1):
            if self.L[i//2]<self.L[i]:
                self.L[i//2],self.L[i]=self.L[i],self.L[i//2]
                i=i//2
            else:
                break
    def value(self):
        if self.N==0:
            return None
        else:
            return self.L[1]
    def heappop(self):
        if self.value()==None:
            return None
        res=self.L[1]
        self.L[1]=self.L[-1]
        self.L.pop()
        self.N-=1
        i=1
        while(i<=self.N):
            if 2*i+1<=self.N:
                if self.L[i]>self.L[2*i] and self.L[i]>self.L[2*i+1]:
                    break
                elif self.L[2*i]<self.L[2*i+1]:
                    self.L[i],self.L[2*i+1]=self.L[2*i+1],self.L[i]
                    i=2*i+1
                else:
                    self.L[i],self.L[2*i]=self.L[2*i],self.L[i]
                    i=2*i
            elif 2*i==self.N:
                if self.L[i]>self.L[2*i]:
                    break
                else:
                    self.L[i],self.L[2*i]=self.L[2*i],self.L[i]
                    i=2*i
            else:
                break
        return res
#ここまでライブラリ
#以降は実装テスト
Q=heaptree()
#Q.heappush(x):xを追加する
#Q.heappop():最大のものを削除する
#Q.value():最大のものを出力する（削除はしない）
#Q.debug:Lを出力する（デバッグ用）
lst=[144, 1, 2, 5, 13, 8, 21, 34, 89, 233, 3, 55,377,0]
for i in lst:
    Q.heappush(i)
    print(Q.debug())

print("#")
while(True):
    tmp=Q.heappop()
    if tmp==None:
        break
    print(tmp,Q.debug())