算法导论打卡3,主要内容:堆排序
def parent(i):
return i//2
def left(i):
return 2*i
def right(i):
return 2*i+1
边的数目
。既然一个包含n个元素的堆可以看作是一颗完全二叉树,那么该堆的高度是O(lgn)
def max_heapify(A,i):
l,r=2*i,2*i+1
heap_size=len(A)-1
if(l<=heap_size and A[l]>A[i]):
largest=l
else:
largest=i
if(r<=heap_size and A[r]>A[largest]):
largest=r
if(largest!=i):
temp=A[i]
A[i]=A[largest]
A[largest]=temp
max_heapify(A,largest)
def build_max_heap(A):
#A[0]存储堆元数个数
for i in range(1,A[0]//2+1)[::-1]:
max_heapify(A,i)
def max_heapify(A,i):
l,r=2*i,2*i+1
heap_size=A[0]
if(l<=heap_size and A[l]>A[i]):
largest=l
else:
largest=i
if(r<=heap_size and A[r]>A[largest]):
largest=r
if(largest!=i):
temp=A[i]
A[i]=A[largest]
A[largest]=temp
max_heapify(A,largest)
def build_max_heap(A):
#A[0]存储堆元数个数
for i in range(1,A[0]//2+1)[::-1]:
max_heapify(A,i)
if __name__ == "__main__":
#数组的第一个位置存储堆元素个数,并用于占位
A=[9,50, 16, 30, 10, 60, 90, 2, 80, 70]
build_max_heap(A)
for i in range(1,A[0]+1):
print(A[i])
def max_heapify(A,i):
l,r=2*i,2*i+1
heap_size=A[0]
if(l<=heap_size and A[l]>A[i]):
largest=l
else:
largest=i
if(r<=heap_size and A[r]>A[largest]):
largest=r
if(largest!=i):
temp=A[i]
A[i]=A[largest]
A[largest]=temp
max_heapify(A,largest)
def build_max_heap(A):
#A[0]存储堆元数个数
for i in range(1,A[0]//2+1)[::-1]:
max_heapify(A,i)
def heapsort(A):
build_max_heap(A)
n=A[0]
for i in range(2,n+1)[::-1]:
temp=A[1]
A[1]=A[i]
A[i]=temp
A[0]-=1
max_heapify(A,1)
A[0]=n
if __name__=="__main__":
#数组的第一个位置存储堆元素个数,并用于占位
A=[9,50, 16, 30, 10, 60, 90, 2, 80, 70]
heapsort(A)
for i in range(1,A[0]+1):
print(A[i])
def heap_maximum(A):
return A[1]
def heap_extract_max(A):
heap_size=len(A)-1
if(heap_size<1):
raise IndexError("heap underflow")
Max=A[1]
A[1]=A[heap_size]
heap_size-=1
max_heapify(A,1)
return Max
def heap_increase_key(A,i,key):
if(key<A[i]):
raise Exception,"new key is small than current key"
A[i]=key
while(i>1 and A[parent[i]]<A[i]):
temp=A[i]
A[i]=A[parent[i]]
A[parent[i]]=temp
i=parent[i]
def max_heap_insert(A,key):
heap_size+=1
A[heap_size]=float('-inf')
heap_increase_key(A,heap_size,key)