- 5th Aug 2022
- 03:27 am
- Admin
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")
line = f.readline()
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()