pythonでヒープを実装してみた

pythonでヒープを実装してみた

#! /usr/local/bin/python
# -*- coding:utf-8 -*-
class Heap:
    
    def maintain_heapify(self,A,i):
        l=2*i+1
        r=2*i+2
        if self.name=='max':
            if l<len(A) and A[l]>A[i]:
                largest=l
            else:
                largest=i
            
            if r<len(A) and A[r]>A[largest]:
                largest=r
            
            if largest!=i:
                A[largest],A[i]=A[i],A[largest]
                self.maintain_heapify(A,largest)

        elif self.name=='min':
            if l<len(A) and A[l]<A[i]:
                smallest=l
            else:
                smallest=i
            if r<len(A) and A[r]<A[smallest]:
                smallest=r
            if smallest!=i:
                A[smallest],A[i]=A[i],A[smallest]
                self.maintain_heapify(A,smallest)

    def build_heap(self,A):
        i=len(A)/2
        while i>=0:
            self.maintain_heapify(A,i)
            i-=1

    def __init__(self,A,name='max'):
        self.name=name
        self.build_heap(A)
        self.heap=A

    def insert(self,v):
        self.heap.append(v)
        self.build_heap(self.heap)

    def deleteroot(self):
        root=self.heap[:1]
        tmp=self.heap[1:len(self.heap)-1]
        self.heap=self.heap[len(self.heap)-1:]+tmp
        self.build_heap(self.heap)
        return root[0]

    def get_root(self):
        return self.heap[0]

使い方はまずHeap(A,'max')かHeap(A,'min')でインスタンスが作れます．Aはリストです．
コンストラクタでヒープを構築しています．

Heap.insert(v)でヒープに新しい値を挿入した後，ヒープを再構築します．vはintです
Heap.deleteroot()でヒープの根(maxで初期化した場合は最大値，minで初期化した場合は最小値)を削除し，その値を返します．
Heap.get_root()でヒープの根を取得します．