## Python Assignment Solution on Objects and Algorithms - Lab 4 Heap

• 5th Aug, 2022
• 15:57 PM

class Heap:

size = 0
arr = []
capacity = 100

def __init__(self):    # Default constructor
self.size = 0
self.arr = [0]*self.capacity

def show(self):
s = ""
for i in range(self.size):
s +=str(self.arr[i])+" "
s +="\n\n"
return s

def min_heapify(self,i):
l = self.left(i)
r = self.right(i)
smallest = i
if (l < self.size and self.arr[l] < self.arr[i]):
smallest = l
if (r < self.size and self.arr[r] < self.arr[smallest]):
smallest = r
if (smallest != i):
temp = self.arr[i]
self.arr[i] = self.arr[smallest]
self.arr[smallest] = temp
self.min_heapify(smallest)

def insert(self,ele):
# print("Insert "+str(ele))
self.size +=1
i = self.size - 1;
self.arr[i] = ele
# print("Heap after insert "+str(ele))

while (i != 0 and self.arr[self.parent(i)] > self.arr[i]):
temp = self.arr[i]
self.arr[i] = self.arr[self.parent(i)]
self.arr[self.parent(i)] = temp
i = self.parent(i)

def deleteMin(self):

if(self.size==0):
return
elif(self.size==1):
self.size -= 1
return self.arr[0]
else:
root = self.arr[0];
self.arr[0] = self.arr[self.size-1]
self.size-=1
self.min_heapify(0)
return root

def empty(self):
return self.size == 0

def getElement(self,index):
return self.arr[index]

def size(self):
return self.size

def parent(self,i):
return (i-1)//2

def left(self,i):
return 2*i

def right(self,i):
return (2*i)+1

def main():

input_files = ["in1.txt","in2.txt","in3.txt","in4.txt"]
output_files = ["out1.txt","out2.txt","out3.txt","out4.txt"]

i = 0 # Loop variable
for filename in input_files:
f = open(filename, "r")
ele_list = line.split(" ")

h = Heap()
write_string = "Heap\n"

for ele in ele_list:
print("i = ",i,"ele = ",ele)
h.insert(int(ele))
write_string += h.show()

# Insert 31
f = open(output_files[i], "w")
write_string +="Insert 31\n"
write_string +="Heap after insert 31\n"
h.insert(31)
write_string += h.show()

# Insert 14
write_string +="Insert 14\n"
write_string +="Heap after insert 14\n"
h.insert(14)
write_string += h.show()

while(not h.empty()):  # As long as the heap is not empty
write_string +="Delete min\n"
write_string +="Heap after Delete min\n"
h.deleteMin()
write_string += h.show()

write_string +="Deleted all\n"

i += 1
f.write(write_string)
f.close()

main()