heapsort python lib


               
               
                #!/usr/bin/env python
__author__ = "lynn lin"
__lience__ = "MIT"
        
class sort_collection(object):
    """
    sort class
    """
    def __init__(self,A=[]):
        self.data = A
        self.heapsize = len(A)
        
    def __left(self,i):
        return  (2*i + 1)
    def __right(self,i):
        return (2*i + 2)
    def __parent(self,i):
        return (i-1)/2
        
    def __max_heapify(self,i):
         l = self.__left(i)
         r = self.__right(i)
         if l  self.heapsize and self.data[l] > self.data:
            largest = l
         else:  
            largest = i
         if r  self.heapsize and self.data[r] > self.data[largest]:
            largest = r
         if largest != i :
            self.data,self.data[largest] = self.data[largest],self.data
            self.__max_heapify(largest)
            
    def __min_heapify(self,i):
         l = self.__left(i)
         r = self.__right(i)
         if l  self.heapsize and self.data[l]  self.data:
            smallest = l
         else:  
            smallest = i
         if r  self.heapsize and self.data[r]  self.data[smallest]:
            smallest = r
         if smallest != i :
            self.data,self.data[smallest] = self.data[smallest],self.data
            self.__min_heapify(smallest)
        
    def build_max_heapify(self):
        for i in range(len(self.data)/2,-1,-1):
            self.__max_heapify(i)
    def build_min_heapify(self):
        for i in range(len(self.data)/2,-1,-1):
            self.__min_heapify(i)
    def heapsort(self,mode = 1):
        """
        default sort order is ascending,if setting mode to 0,the sort order is descending
        """
        if mode == 1:
            self.build_max_heapify()
        else :
            self.build_min_heapify()
        length = len(self.data)
        for i in range(length-1,0,-1):
            self.data,self.data[0] = self.data[0],self.data
            self.heapsize -= 1
            if mode == 1:
                self.__max_heapify(0)
            else:
                self.__min_heapify(0)
               
    def heap_maximum(self):
        return self.data[0]
    def heap_minimum(self):
        return self.data[0]
    def heap_extract_min(self):
        if self.heapsize  1 :
            raise
        min = self.data[0]
        self.data[0] = self.data[self.heapsize-1]
        self.heapsize -= 1
        self.__min_heapify(0)
        return min
   
    def heap_extract_max(self):
        if self.heapsize  1 :
            raise
        max = self.data[0]
        self.data[0] = self.data[self.heapsize-1]
        self.heapsize -= 1
        self.__max_heapify(0)
        return max
   
    def heap_increase_key(self,i,key):
        if key  self.data:
            raise
        self.data = key
        while i > 0 and self.data[self.__parent(i)]  self.data:
            self.data[self.__parent(i)],self.data = self.data,self.data[self.__parent(i)]
            i = self.__parent(i)
        
               
   
if __name__ == '__main__':
    A=[1,7,5,0,2]
    x = sort_collection(A)
    x.build_max_heapify()
    ma = x.heap_extract_max()
    mb = x.heap_extract_max()
    mc = x.heap_maximum()
    print ma,mb,mc