|
#!/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[i]:
largest = l
else:
largest = i
if r < self.heapsize and self.data[r] > self.data[largest]:
largest = r
if largest != i :
self.data[i],self.data[largest] = self.data[largest],self.data[i]
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[i]:
smallest = l
else:
smallest = i
if r < self.heapsize and self.data[r] < self.data[smallest]:
smallest = r
if smallest != i :
self.data[i],self.data[smallest] = self.data[smallest],self.data[i]
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[i],self.data[0] = self.data[0],self.data[i]
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[i]:
raise
self.data[i] = key
while i > 0 and self.data[self.__parent(i)] < self.data[i]:
self.data[self.__parent(i)],self.data[i] = self.data[i],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
|
