Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def check_for_min_heap(arr):
- arr_cpy=arr[0:len_arr]
- for i in range(len_arr//2-1,-1,-1):
- p=i
- left_ind=p*2+1
- right_ind=2*p+2
- while(left_ind<=len_arr-1 or right_ind<=len_arr-1):
- if (left_ind>len_arr-1):
- m=right_ind
- elif (right_ind>len_arr-1) :
- m=left_ind
- else :
- m=arr_cpy.index(min(arr_cpy[left_ind],arr_cpy[right_ind]))
- if (arr_cpy[p]>arr_cpy[m]):
- temp=arr_cpy[p]
- arr_cpy[p]=arr_cpy[m]
- arr_cpy[m]=temp
- p=m
- left_ind=p*2+1
- right_ind=2*p+2
- else:
- break
- for i in range(0,len_arr):
- if arr[i]!=arr_cpy[i]:
- return False
- return True
- def heapify(arr):
- global len_arr
- for i in range(len_arr//2-1,-1,-1):
- p=i
- left_ind=p*2+1
- right_ind=2*p+2
- while(left_ind<=len_arr-1 or right_ind<=len_arr-1):
- if (left_ind>len_arr-1):
- m=right_ind
- elif (right_ind>len_arr-1) :
- m=left_ind
- else :
- m=arr.index(min(arr[left_ind],arr[right_ind]))
- if (arr[p]>arr[m]):
- temp=arr[p]
- arr[p]=arr[m]
- arr[m]=temp
- p=m
- left_ind=p*2+1
- right_ind=2*p+2
- else:
- break
- for i in range(0,len_arr):
- print(arr[i],end=" ")
- print()
- def Insert_an_element(arr,element):
- global len_arr
- if (check_for_min_heap(arr)==False or len_arr==0):
- print("Heap does not exist")
- else:
- arr[len_arr]=element
- len_arr=len_arr+1
- heapify(arr)
- def delete_min_element(arr):
- global len_arr
- if (check_for_min_heap(arr)==False or len_arr==0):
- print("Heap does not exist")
- else:
- arr[0]=arr[len_arr-1]
- arr[len_arr-1]=0
- len_arr=len_arr-1
- heapify(arr)
- def delete_particular_element(arr,m):
- global len_arr
- if (check_for_min_heap(arr)==False):
- print("Heap does not exist")
- elif (m not in arr):
- print("Integer not found")
- else:
- d=arr.index(m)
- arr[d]=arr[len_arr-1]
- len_arr=len_arr-1
- heapify(arr)
- def heap_sort(arr):
- global len_arr
- bound=len_arr-1
- while(bound!=0):
- temp=arr[bound]
- arr[bound]=arr[0]
- arr[0]=temp
- len_temp=bound
- for i in range(len_temp//2-1,-1,-1):
- p=i
- left_ind=p*2+1
- right_ind=2*p+2
- while(left_ind<=len_temp-1 or right_ind<=len_temp-1):
- if (left_ind>len_temp-1):
- m=right_ind
- elif (right_ind>len_temp-1) :
- m=left_ind
- else :
- m=arr.index(min(arr[left_ind],arr[right_ind]))
- if (arr[p]>arr[m]):
- temp=arr[p]
- arr[p]=arr[m]
- arr[m]=temp
- p=m
- left_ind=p*2+1
- right_ind=2*p+2
- else:
- break
- bound=bound-1
- for i in range(0,len_arr):
- print(arr[i],end=" ")
- print()
- len_arr=0
- arr=[0 for i in range(0,100)]
- menu=0
- while(menu!=-1):
- input_arr=list(map(int,input().split(" ")))
- menu=input_arr[0]
- if (menu==1):
- for i in range(2,len(input_arr)):
- len_arr=len_arr+1
- arr[i-2]=input_arr[i]
- heapify(arr)
- elif (menu==2):
- element_to_be_inserted=input_arr[1]
- Insert_an_element(arr,element_to_be_inserted)
- elif(menu==3):
- delete_min_element(arr)
- elif(menu==4):
- m=input_arr[1]
- delete_particular_element(arr,m)
- elif(menu==5):
- heap_sort(arr)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement